** correction rapide de la feuille de td 2bis ** --- Exercice 3, pour passer de la grammaire à l'automate, le cours dit que l'on prend un symbole par état, S pour l'état initial, et qu'ensuite (voir page 78-82) ... cela donne pour le deuxième : S->aA_2 A_2->aA_2 | bA_2 | cA_2 | b (et c'est tout) pour le premier automate, pour se mettre dans les conditions de la construction du cours, il ne faut pas avoir d'epsilon-transitions, donc, avant de faire des erreurs, les enlever. -- Exercice 4 Les yeux avertis auront vu que cette grammaire n'est pas de type 3. En effet, la règle S->cc n'est pas permise. Il n'existe donc pas de construction automatique de de type de grammaire vers un automate fini, car sinon on aurait l'implication algébrique => régulier, ce qui n'est pas le cas !!! En revanche, rien ne dit que pour cette grammaire PARTICULIERE, un automate n'existe pas. Pour voir, essayer de décrire le langage engendré par cette grammaire, et voir si par hasard il serait régulier.