Langages réguliers et hors-contexte
Cours M1 INaLCO, 2008-2009
Interrogation écrite du 18/12/08
N.B. Les expressions régulières sont écrites avec la syntaxe étendue "à la LEX".
1. Construire et justifier un automate fini, déterministe et minimal reconnaissant le langage
des commentaires en fin de ligne, décrit par l'expression régulière : "//[^\n]*\n".
Le représenter graphiquement avec la convention utilisée par le logiciel automates
(ne pas montrer l'éventuel état-poubelle).
2. On rappelle que la notation [*] , qui peut aussi s'écrire \*, désigne le caractère '*'
et non l'opérateur étoile,
mais que, en dehors des crochets, '*' désigne bien l'opérateur étoile !
Sachant que l'expression régulière des "commentaires en C" :
"/[*]([^/*]|[/]|[*]+[^/*])*[*]+/"
correspond à l'automate ci-dessous
(déterministe minimal), où la lettre a représente l'ensemble [^/*] :
en utilisant le résultat de la question 1, construire un automate déterministe reconnaissant la réunion
(/[*]([^/*]|[/]|[*]+[^/*])*[*]+/)|(//[^\n]*\n).
En déduire l'automate minimal reconnaissant cette expression, et le représenter graphiquement
avec la convention rappelée à la question 1.