THL Flashcards
C’est quoi une alphabet?
un ensemble fini non vide de symboles
c’est quoi la notation d’une alphabet?
sa notation est : X
c’est quoi un mot?
une suite d’element de X
c’est quoi la notation du mot?
c’est : omega
c’est quoi le mot vide?
c’est une notion théorique appelé epsilon dont la longueur est 0
c’est quoi la longueur d’un mot?
la longueur du mot est : |omega|= somme des occurrences des différents symboles du mot
c’est quoi X*?
c’est ensemble de tout les mots possible avec l’alphabet X dont la longueur est >= 0 (infini)
c’est quoi X+ ?
c’est ensemble de tout les mots possible avec l’alphabet X dont la longueur est > 0 (sauf epsilon)
(infini)
C’est quoi la relation de X* avec X+?
X* = X+ U epsilon
C’est quoi X n ?
C’est les mots de longueur n avec quelque soit le nombre d’element de cette alphabet
que peut-on dire sur la dépendance des elements d’une alphabet ?
dans le cas de X* par exemple , il n y a pas de dependence ente les elements , pour X+ aussi et meme X n
Donne une autre écriture de X(n+1)
X(n+1) = X n . X
Que représente le point entre les alphabets?
C’est le point de concatenation
c’est quoi un langage formel?
un ensemble de mot omega appartenant à X ,et toute partie de X*
quel sont les types de langages?
3 types : fini (langage théorique) , infini (les langage de programmation), vide
comment décrire les différents types de langages?
- 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
langage propre?
epsilon - libre
c’est le facteur gauche d’un langage?
FG(L) = { ω1 ∈ X* / ∃ ω2 ∈ X* et ω1.ω2 ∈ L }
c’est quoi une grammaire?
un quadruplet G = <X,N,S,P>
que représente chaque element du quadruplet de G?
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
la diff entre les terminaux et les non terminaux?
on peut deriver des langages à partir des non terminaux mais on ne peut pas les deriver à partir des terminaux
Où trouver l’axiome de la grammaire?
C’est le membre gauche non terminal de la première règle de production (MGP)
quel est la forme d’une règle de production?
A → α
- A est appelé Membre Gauche de la Production (MGP)
- α est appelé Membre Droit de la Production (MDP)
que veut dire un * au dessus de la flèche dans la règle de production?
un nombre 1 ou plus de derivation pour trouver ce mot
notion de derivation?
2 types : directes et indirecte
diff entre les types de derivation ?
directe vient d’une règle de production et indirecte vient de l’application de plusieurs règles de production
que peut-on faire avec des règles de meme MGP?
on peut les regrouper avec un slash (/)
un mot générée?
il existe un dérivation directe ou indirecte à partir de S donnant ω ∈ X*
langage générée?
L(G) = { ω ∈ X* / S → ω }
relation entre grammaire et langage?
la grammaire génère le langage
relation entre automate et langage?
l’automate reconnait le langage
equivalence entre grammaire?
Deux grammaires sont dites ́équivalentes si et seulement si elles génèrent le meme langage.
element neutre de la concatenation?
Epsilon
automate finis?
Un automate A simple et fini est défini par un quintuplé :
A =< X, Q, I, F, δ >
que représente chaque element du quintuplé de l’automate?
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.
rep algébrique d’un automate?
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)}
rep graphique d’un automate?
Tout automate a une representation algébrique et une representation graphique correspondante.
comment peut l’automate savoir si un mot et reconnu par lui?
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).
langage reconnu par un automate?
automate est constitu ́e de l’ensemble des mots reconnus
par cet automate. Formellement : L(A) = {ω ∈ X∗/q0 −→w qf , q0 ∈ I, qf ∈ F}
what is état accessible?
∃q0 ∈ I et ω ∈ X* tel que :q0→w q.
état inaccessible?
Tout état inaccessible doit être supprimé de l’automate.
Automate déterministe?
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.
rmrq
Passage d’un automate à une grammaire :
- 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.
