Exercice

Ceci est une adaptation d'un exercice de Mohri, Pereira et Riley, trouvé sur la page web de FSM.

Question 1

On se donne l'alphabet {a,b,c,d,A,B,C,D,<espace>} On représentera l'espace par un caractère ou une chaîne arbitraire (on ne peut pas utiliser réellement un caractère espace, car il est utilisé comme séparateur dans les fichiers textes). En utilisant FSM et Lextools, créez les automates suivants:

1. un automate qui reconnaît les chaînes de longueur 1.
2. un automate qui reconnaît un espace.
3. un automate qui reconnaît les mots qui commencent par une majuscule et dont les autres symboles sont des lettres en minuscule. On les appelera mots majuscules.
4. un automate qui reconnaît tous les mots comportant un a.

Question 2

En utilisant les automates de la question 1 et les opérations de FSM, créez les automates suivants.

1. un automate qui reconnaît un série de mots majuscules suivis d'un espace (un espace après chaque mot).
2. un automate qui reconnaît les mots majuscules et comportant la lettre a.
3. un automate qui reconnaît les mots majuscules ou les mots qui ne contiennent pas a.
4. même question, mais sans utiliser fsmunion.

Question 3

Pour chacun des automates de la question 2, supprimez les epsilons, déterminisez et minimisez. Donnez le nombre d'états et de transitions avant et après ces opérations.