TD1 - Automates et Langages - RICM

Exercice. Un simple automate.

Pour l'automate representé par ce diagramme de transitions

1. Ecrire:
  • Les états de l'automate (Q)
  • L'alphabet(Sigma)
  • L'état initial (q0)
  • Les états finaux (F)
  • Et bien sûr les transitions (delta)

2. Quels sont les calculs de l'automate sur les mots suivants: 101, 0100, epsilon, 0110110? 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 choux.

Mr. M. amène le loup L., la chèvre C. le choux 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é

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:

Exercice. Encore quelques automates à construire.

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

TD2 TD3 TD4 TD5 TD7

Retour