Langages réguliers et hors-contexte
Cours M1 INaLCO, 2013-2014
Interrogation écrite du 28/11/2013
Les deux parties sont indépendantes, traitez-les dans l'ordre qui vous
convient.
Première partie
On veut repérer dans un texte en XML les entités-caractères, comme "ø
" ou "æ
"
qui permettent d'écrire en ASCII pur "A.P. Møller-Mærsk
" pour signifier
"A.P. Møller-Mærsk".
- On s'occupe d'abord de décrire les entités individuellement, par l'expression "
&#[0-9]+;
".
Construire un automate fini déterministe minimal reconnaissant le langage ainsi décrit.
- Déduire de cet automate un automate reconnaissant les séquences d'entités "
(&#[0-9]+;)+
".
- Dans les séquences acceptées, on souhaite autoriser des blancs (en quantité variable)
entre les entités.
Comment faut-il écrire l'expression régulière correspondante ?
Comment faut-il modifier l'automate construit en 2. ?
-
Seconde partie
On considère le programme C++ ci-joint, écrit à partir d'un automate fini par le procédé décrit
au cours n°7.
- Dessiner l'automate en question (en précisant l'état initial et les états terminaux).
- Cet automate est-il minimal ?
Sinon, le réduire, et modifier le programme pour qu'il traduise l'automate minimal.
- Proposer une expression régulière décrivant le langage reconnu par cet automate.
Appelons L ce langage.
- Comment faut-il modifier le programme pour qu'il accepte L* ?
Et pour qu'il accepte les séquences de mots de L avec entre eux des blancs
en quantité variable ?