TD1 - Automates et Langages - RICM

Exercice. Un simple automate.

Pour l'automate représenté par ce diagramme de transitions

1. Ecrire: Les états de l'automate (Q) L'alphabet(S) L'état initial (q0) Les états finals (F) Et bien sûr les transitions (d)

2. Quels sont les calculs de l'automate sur les mots suivants: 101, 0100, e, 011111? Lesquels de ces mots sont acceptés?

3. Caractériser tous les mots acceptés par cet automate (son langage)

Problème. Le loup, la chèvre et le chou.

Mr. M. amène le loup L., la chèvre C., le chou H. au bord de la rivière qu'il veut traverser dans un bateau. Le bateau et tellement petit, que l'homme rentre dedans seul ou avec un seul compagnon. Sans surveillance humaine L. mange immédiatement C., et C. mange H. Comment toute l'équipe peut traverser la rivière?

Méthode de solution: 1. Construire un automate A qui modélise la situation. Il faut retrouver à partir de l'énoncé

• Les états de l'automate (Q)
• Les actions possibles (S)
• L'état initial (q₀)
• Les états finaux (F)
• Et bien sûr les transitions (d)

N'oubliez pas qu'il faut dessiner tous ces éléments sur un "diagramme de transitions".

2. Trouver comment traverser la rivière.

Deux questions théoriques:

• Est-ce que l'automate A correspond à la définition de l'automate déterministe vue en cours?
• Quel est le "sens physique" du langage accepté par l'automate A?

Exercice. Encore quelques automates à construire.

Construire, si possible, les automates déterministes qui reconnaissent les langages suivants sur l'alphabet {a,b}

• Tous les mots sans b.
• Tous les mots avec le prefixe ab.
• Tous les mots avec le suffixe ab.
• Tous les mots dans lesquels chaque a et suivi d'un b.
• Tous les mots qui contiennent autant de a que de b.

Retour