THL

Question 1

C’est quoi une alphabet?

Answer 1

un ensemble fini non vide de symboles

Question 2

c’est quoi la notation d’une alphabet?

Answer 2

sa notation est : X

Question 3

c’est quoi un mot?

Answer 3

une suite d’element de X

Question 4

c’est quoi la notation du mot?

Answer 4

c’est : omega

Question 5

c’est quoi le mot vide?

Answer 5

c’est une notion théorique appelé epsilon dont la longueur est 0

Question 6

c’est quoi la longueur d’un mot?

Answer 6

la longueur du mot est : |omega|= somme des occurrences des différents symboles du mot

Question 7

c’est quoi X*?

Answer 7

c’est ensemble de tout les mots possible avec l’alphabet X dont la longueur est >= 0 (infini)

Question 8

c’est quoi X+ ?

Answer 8

c’est ensemble de tout les mots possible avec l’alphabet X dont la longueur est > 0 (sauf epsilon)
(infini)

Question 9

C’est quoi la relation de X* avec X+?

Answer 9

X* = X+ U epsilon

Question 10

C’est quoi X n ?

Answer 10

C’est les mots de longueur n avec quelque soit le nombre d’element de cette alphabet

Question 11

que peut-on dire sur la dépendance des elements d’une alphabet ?

Answer 11

dans le cas de X* par exemple , il n y a pas de dependence ente les elements , pour X+ aussi et meme X n

Question 12

Donne une autre écriture de X(n+1)

Answer 12

X(n+1) = X n . X

Question 13

Que représente le point entre les alphabets?

Answer 13

C’est le point de concatenation

Question 14

c’est quoi un langage formel?

Answer 14

un ensemble de mot omega appartenant à X ,et toute partie de X*

Question 15

quel sont les types de langages?

Answer 15

3 types : fini (langage théorique) , infini (les langage de programmation), vide

Question 16

comment décrire les différents types de langages?

Answer 16

• vide : o/
• fini : énumérer ses mots
• infini :
  1. application des operations à des langages simples
  2. un ensemble de règles de production de grammaires

Question 17

langage propre?

Answer 17

epsilon - libre

Question 18

c’est le facteur gauche d’un langage?

Answer 18

FG(L) = { ω1 ∈ X* / ∃ ω2 ∈ X* et ω1.ω2 ∈ L }

Question 19

c’est quoi une grammaire?

Answer 19

un quadruplet G = <X,N,S,P>

Question 20

que représente chaque element du quadruplet de G?

Answer 20

X : les terminaux (tjrs miniscule)
N : les non terminaux (tjrs MAJ)
S : l’axiome de la grammaire
P : les règles de la production de la grammaire

Question 21

la diff entre les terminaux et les non terminaux?

Answer 21

on peut deriver des langages à partir des non terminaux mais on ne peut pas les deriver à partir des terminaux

Question 22

Où trouver l’axiome de la grammaire?

Answer 22

C’est le membre gauche non terminal de la première règle de production (MGP)

Question 23

quel est la forme d’une règle de production?

Answer 23

A → α
- A est appelé Membre Gauche de la Production (MGP)
- α est appelé Membre Droit de la Production (MDP)

Question 24

que veut dire un * au dessus de la flèche dans la règle de production?

Answer 24

un nombre 1 ou plus de derivation pour trouver ce mot

Question 25

notion de derivation?

Answer 25

2 types : directes et indirecte

Question 26

diff entre les types de derivation ?

Answer 26

directe vient d'une règle de production et indirecte vient de l'application de plusieurs règles de production

Question 27

que peut-on faire avec des règles de meme MGP?

Answer 27

on peut les regrouper avec un slash (/)

Question 28

un mot générée?

Answer 28

il existe un dérivation directe ou indirecte à partir de S donnant ω ∈ X*

Question 29

langage générée?

Answer 29

L(G) = { ω ∈ X* / S → ω }

Question 30

relation entre grammaire et langage?

Answer 30

la grammaire génère le langage

Question 31

relation entre automate et langage?

Answer 31

l'automate reconnait le langage

Question 32

equivalence entre grammaire?

Answer 32

Deux grammaires sont dites ́équivalentes si et seulement si elles génèrent le meme langage.

Question 33

element neutre de la concatenation?

Answer 33

Epsilon

Question 34

automate finis?

Answer 34

Un automate A simple et fini est défini par un quintuplé : A =< X, Q, I, F, δ >

Question 35

que représente chaque element du quintuplé de l'automate?

Answer 35

X : Alphabet Q : ensemble des états I ⊆ Q : Ensemble des états initiaux ; F ⊆ Q : Ensemble des états finaux ; δ ⊆ Q ∗ X ∗ Q : Ensemble des transitions entre états.

Question 36

rep algébrique d'un automate?

Answer 36

A =< X, Q, I, F, δ > défini par : - X = {a, b} - Q = {q1, q2} - I = {q1} - F = {q2} - δ = {(q1, a, q1),(q1, b, q2),(q2, b, q2),(q2, a, q1)}

Question 37

rep graphique d'un automate?

Answer 37

Tout automate a une representation algébrique et une representation graphique correspondante.

Question 38

comment peut l'automate savoir si un mot et reconnu par lui?

Answer 38

Le processus commence par l’un des états initiaux q0 de l’ensemble I. - Les symboles du mot sont lus les uns après les autres. - A la lecture de chaque symbole, le processus cherche à appliquer une des transitions de l’ensemble δ pour se déplacer vers le prochain état (en utilisant l’etat actuel et le caractère qui vient d'être lu). - Le mot est reconnu si et seulement si le dernier état atteint (à la lecture du dernier caractère du mot) est un état final (de F).

Question 39

langage reconnu par un automate?

Answer 39

automate est constitu ́e de l’ensemble des mots reconnus par cet automate. Formellement : L(A) = {ω ∈ X∗/q0 −→w qf , q0 ∈ I, qf ∈ F}

Question 40

what is état accessible?

Answer 40

∃q0 ∈ I et ω ∈ X* tel que :q0→w q.

Question 41

état inaccessible?

Answer 41

Tout état inaccessible doit être supprimé de l’automate.

Question 42

Automate déterministe?

Answer 42

ssi : - Il est simple (transitions uniquement par des symboles de l’alphabet) ; - Etat initial unique (|I| = 1) ; - Transitions uniques : A partir de tout état q, on ne peut pas aller par le meme symbole vers deux états différents. Formellement : ∀q1, q2, q3 ∈ Q : Si (q1, a, q2) ∈ δ et (q1, a, q3) ∈ δ ⇒ q2 = q3.

Question 43

rmrq

Question 44

Passage d’un automate à une grammaire :

Answer 44

- Tout non-terminal de la grammaire lui correspond un ́état dans l’automate. - Toute transition dans un automate, à partir d’un état q1 par un symbole a vers un état q2, est traduite comme suit : q1 → aq2. — Pour tout état final qf de l’automate, on doit ajouter dans la grammaire correspondante la règle : qf → ε. — Les meme règles peuvent être appliquées dans l’ordre inverse pour le passage d’une grammaire à un automate, mais pas pour toutes les grammaires, car certaines grammaires n’ont pas d’automate equivalent.