Théorie des langages : Exercices automates minimisation
Télécharger PDFExercice : peut-on prouver l'égalité des langages grâce à l'algorithme de minimisation? On considère l'alphabet Σ = {a}. Q1. Donnez deux automates minimaux, chacun avec deux états et deux transitions, qui reconnaissent le même langage Σ+, mais qui sont di érents. Q2. Choississez un des deux automates et démontrez qu'il est minimal. Égalité de langages et comparaison d'automates On considère deux automates A1 et A2, on aimerait montrer que L(A1) = L(A2), c'est-à-dire que A1 et A2 reconnaissent le même langage. Un étudiant propose le principe suivant : 1. On minimise A1 pour obtenir un automate minimal AM 1 2. On minimise A2 pour obtenir un automate minimal AM 2 3. On véri e que les automates minimisés sont identiques An de savoir si ce principe est valide, posons nous quelques questions : Q3. Complétez les raisonnements suivants sans justi cation, répondez sur votre feuille 1. si AM 1 = AM 2 que peut-on conclure sur L(AM 1 ) et L(AM 2 )? 2. L(A1) . . . . .... 3. L(AM 2 ) L(AM 1 ) . . . . .... L(A2) 4. si AM 1 = AM 2 que peut-on conclure sur L(A1) et L(A2)? Q4. Répondez et justi ez votre réponse Si L(A1) = L(A2), que peut-on dire des automates minimisés AM 1 et AM 2 ? Q5. Complétez la conlusion Conclusion 1. Si les automates . . . . ..............