Théorie des Langages - 2
vendredi 11 avril 2014
09:13
L est le langage des mots qui se terminent par b
L={b,ab,bb,aab,abb,bab,bbb,...}
Il existe un algorithme qui prend un automate non deterministe quelconque et retourne un automate déterministe qui connait le même langage.
Soit L le langage des mots sur E = {m,a,b,x} qui se terminent par man.
1)Donner un automate non détrministe le plus simple possible qui reconnaît L.
2)Donner un automate déterministe qui reconnaît L.
L={man,aman,nman,xman,mman, mnman,15 autres mots de taille 5, etc…}
1)
Etape Q0: Boucler jusqu'à trouver m
Q1: Voir si a
Q2: voir si n
Q3: Fini!
2)Pour passer à un automate déterministe,
   détailler tous les états à chaque étape. 
Soit E = {a,b}
L1 est le langage des mots qui se terminent par b.
L2 est _________________ dont l'avant-dernière lettre est un b. 
L3 est _________________ dont l'antépénultième lettre est un b.
Lk est _________________ dont la kième lettre avant la fin est un b.
Version non-déterministe de Lk: automate à k+1 états.
Soit E = {0,1}
Donner un automate déterministe qui reconnaît le langage des nombres(en binaire) divisibles par 3.
L = {0,00,11,000,011,110,…}
Ajout d'un 0 à X en binaire: 2X
Ajout d'un 1: 2X + 1
Modulos etc.
Tests: 11,110,1001,1100,1111,10010
{q0}
{q0 ou q1}
{q0 ou q2}
{q0 ou q3}