TL

Pour rappel

Une grammaire G est un quadruplet (N,T,X,R) où

N est le vocabulaire des non-terminaux (notés généralement avec des majuscules) ;

T est un vocabulaire des terminaux (notes genéralement avec des minuscules) et N ∩ T = ∅

X ∈ N est un non-terminal appelé l’axiome ;

R est un ensemble de règles de production de la forme α → β avec α un mot de V + et β un mot de V ∗ , o`u V = N ∪ T .

(Non terminal, Terminal, aXiome, règles de production)

Pour simplifier

T c'est les lettres du vocabulaire donc ici a et b d'où {a,b}

Pour X on laisse X car on le définira dans les règles de production

Vu q'uon veut a*b* on va définir une première règle de production A-> aA|ε . Cette règle de production représente a* car on peut mettre une infinité de a (boucle aA) et on peut s'arrêter à n'importe quel moment (|ε)

On fait pareil avec b* en nommant la règle de production B.

Le rôle de l'axiome est de permettre de fabriquer des phrases du langage en partant de l'élément initial. On veut représenter a*b* on a donc besoin de la règle de production A et B. Pour avoir a*b* on a donc X=AB.

Ansi R devient {X->AB,A->aA/ε,B->bB/|ε}

Pour N on écrit le symbole des règles de productions

Définition 1 Une grammaire algébrique G est une grammaire (N, T, X, R) avec N ∩T = ∅ et R un ensemble de règles de productions A → α avec A ∈ N , α ∈ (N ∪ T )∗.

La magie opère

Le langage engendré par l'expression de gauche est une sous partie du langage engendré par l'expression de droite

En fait, (a+b)* c'est "tu prends a ou b (parce que a+b) et tu reproduis cette opération un nombre de fois compris entre 0 et l'infini (parce que * et pas + )

Donc ça peut donner a, aaaaaaaa, epsilon, abababa, bbbbbbb, b.... bref t'as l'idée, toute suite de a et de b, y compris vide

yep, Big Brain Logic

On commence par créer un automate représentant l'expression régulière minimal (on enlève .(ba)* car ça peut être ε , on enlève (ab)* car ça peut être ε et on enlève + ∅* car ça peut aussi être + ∅*

On commence donc par représenter ab d'où 0->2->5 soit ab.

On réduit la minimisation de l'expression régulière en prenant en compte le premier .(ba)*. On représente donc a.(ba)*.b

Maintenant on prend toute l'expression régulière en compte et on obtient l'automate ci-dessus.

Pour compléter cet automate on remarque que l'on a 2 fois la même chose dans l'automate A réaliser à la q1. On va deux fois vers a : une fois pour pour 0->1 et 0->2. On marque donc 0->{1,2}.

En partant de 1 ou de 2 on va en b vers 3 , 4, 5. d'où {3,4,5}

a revient de 4 à 2 et de 3 à 1. On met donc un a de {3,4,5} vers {1,2}.

Et voilà, on a compléter nôtre automate. Il est maintenant déterministe.

un automate est complet si les transitions depuis chaque état pour chaque caractère d'entrée sont toutes présentes

Là, depuis 0, tu peux aller nulle par avec un b : donc R(0,b) (l'ensemble des endroits où on va depuis 0 avec un b) est l'ensemble vide, donc l'automate n'est pas complet (faut lui rajouter un puits pour le compléter)

On a jamais demandé à ce que la réponse à la question 3 soit un automate complet, juste un automate déterministe

(ie on n'a jamais à choisir entre deux états à partir d'un état de départ et d'un caractère qu'on lit)

Remarque : Un ́etat d’erreur (ou état-puits) sert à indiquer l'état-cible si les choses tournent mal : on est dans un ́etat et on lit une lettre que l’on ne doit pas pouvoir lire dans cet ́etat. On met une transition qui mène vers un ́etat-puits (on ne sort jamais). De plus, cela sert à compléter un automate sans changer le langage qu’il reconnaît

Pour minimiser l'automate il faut qu'il soit complet donc il faut qu'on ajoute dans cet automate un état d'erreur.

Pour minimiser un automate, on crée un tableau dont les colonnes sont les différents états de l'automate.

Soient I la classe des ́etats d’acceptation (2 ronds), II la classe d’états non finaux (1 rond),. La table ci-dessous représente la minimisation de l’automate A init.

Pour expliquer les diférentes lignes du tableau, le bilan epsilon c'est quand on reste sur l'état donc on reste sur le même état. a c'est quand on part de l'état avec la lettre a vers un autre automate. Même chose pour b. Pour le bilan on représente les différentes combinaisons par un symbole. maintenant l'état 1 se note I , l'état 2 II, l'état 3 III et l'état 4 IV. Pour le slignes d'après on a par exemple pour l'état 2 on va en 4 avec la lettre a on marque donc l'état IV. On renote les différentes combinaisons et si on est sur la même sorte de combinaisons on a fini le tableau.

On conclut par Stabilisation à 4 états donc Amin=A.

pour répondre facilement à la question 3 le complément d'un langage c'est son automate où on remplace les états d'acceptation par les états non finaux. Même principe avec les états non finaux remplacés par les états d'acceptation.

Pour info suivant(ε)=#

premier(X)={a,b}. on a d'abord X->SaS on remplace d'abord S par ε. On arrive donc à X->aS. Donc premier(aS)=a. On remplace ensuite S par bSa. premier(bSa)=b.

S=ε ou bSa car premier(ε)=ε et premier(bSa)=b.