Langages réguliers et hors-contexte Cours
M1 INaLCO, 20010-2011
Interrogation écrite du 07/12/2010
-
Première partie
On considère un alphabet à deux lettres a
et b
,
et l'automate suivant sur cet alphabet :
Les états de l'automate sont étiquetés X, Y, Z, T et U, l'état initial
est X, le seul état terminal est Y.
Appelons A cet automate.
- L'automate A est-il
déterministe ?
Si oui, donnez sa table de transitions.
Exemple :
- L'automate A est-il minimal ?
Si non, réduisez-le et donnez l'automate minimal qui reconnaît le même
langage.
- Donnez une expression régulière décrivant le langage
reconnu
par l'automate A .
-
Deuxième partie
On considère l'automate B
non-déterministe à 5 états I, II, III,
A, B, où I est l'état initial et I, III, B les états terminaux.
- Que pouvez-vous dire du langage reconnu par l'automate B ?
En d'autres termes, donnez a priori une forme d'expression
régulière pour ce langage.
- Reste à déterminer le langage reconnu par l'automate C que voici
Vérifiez que (a*b)*
= Σ*b ∪ {ε
}, où Σ
désigne
l'alphabet {a, b
}, cela peut vous aider...
- Montrez que l'automate déterministe associé à l'automate B n'est autre que l'automate A qui a été envisagé dans la première partie.
Pouvez-vous en déduire une autre réponse à la question I.3 ?