Théorie des langages : Td 1 automate fini déterministe
Télécharger PDFL3 - Langages et Compilation1
TD 1 - Automate fini d ́eterministe
Qu 1.Donner la table de transition de l’AFD suivant.12 ab ba Quel est le langage reconnu par cet automate ?
Qu 2.Quel est le langageLreconnu par l’automate suivant ?aaa Construire l’automate qui reconnaˆıt le compl ́ementaire{a,b}∗ \L
Qu 3.Soit l’AFD ({a,b},{1,2,3,4},δ,1,{4}) avecδdonn ́e par la table suivante :ab →112232 314432 Le dessiner. D ́eterminer le langage reconnu par cet AFD ?
Qu 4.Donner les expressions r ́eguli`eres correspondant aux langages suivants et construire des
AFD qui les reconnaissent.a.L={ε} b.L=φ
c.L={a,b}∗ d.L={ab}{a,c}{b}+ e.L={a,b}∗ {a}{a,b}2 f.L1 ={a,bb}∗ ,L2 ={b}∗ {{a}{b}∗ {a}}∗ {b}∗ etL1 ∩L2 Qu 5.Soit le langage finiX={aa,abaaa,abab}.
a.D ́eterminer Pref(X) l’ensemble des pr ́efixes des mots deX.
b.D ́eterminer un AFD qui reconnaisseX.
c.G ́en ́eralisation. Montrer que tout ensemble fini de mots est r ́egulier.
d.Construire un AFD qui reconnaisse{a,b}∗ X.
e. ́
Ecrire un algorithme qui prend en entr ́ee la table de transition de l’AFD pr ́ec ́edente et un
textet(un mot!) et qui signale toutes les occurrences des mots deXdanst.
Qu 6.Montrer que les langages suivants ne sont pas rationnels.a.L={a p
:ppremier}
b.L={w∈{a,b}∗ :]a (w) =]b (w)}]a (w) le nombre deadansw