Langages réguliers et hors-contexte
Cours M1 INaLCO, 2008-2009
Interrogation écrite du 11/12/08
On considère l'alphabet X = {0, x, 7, 9, h},
et l'expression régulière suivante sur cet alphabet,
écrite en syntaxe
standard du logiciel automate :
E = (7|9)+|0(7+|x(7|9|h)+)
Transcrire cette expression en notation mathématique (avec "∪" pour la réunion et "." pour le produit).
Les deux sous-ensembles (7|9)+ et 0(7+|x(7|9|h)+) sont-ils disjoints ?
Les mots suivants appartiennent-ils au langage de l'expression, et pourquoi ?
779, 0779, 779h, 0779h, 0x779h, h779, 0h779, 0xh779
On considère l'automate fini sur le même alphabet
Cet automate est-il déterministe ?
Si oui, est-il minimal ?
A-t-il quelque rapport avec l'expression précédente ?
Avez-vous une interprétation raisonnable pour cette expression ?