Eléments d’ informatique théorique Série 4

Exercice 4.1 Ecrire une grammaire régulière pour générer le langage L = {0(10)^{n}|n ≥ 0} et donner l’AF correspondant.

Exercice 4.2 Ecrire une grammaire régulière engendrant le langage défini par :

q_{0}  q_{1} q_{2}  q_{3} q_{f} a b  b  a b  a cc b

Exercice 4.3 Les grammaires suivantes ne sont pas régulières mais engendrent bien des langages réguliers. Donnez des grammaires régulières qui engendrent ces mêmes langages.

1. \begin{matrix}S & ⟶ & XY \\ X & ⟶ & aX | Xa | a \\ Y & ⟶ & aY | Y a | a \end{matrix}

2. \begin{matrix}S & ⟶ & XY Z \\ X & ⟶ & aX | bX | ϵ \\ Y & ⟶ & aY | bY | ϵ \\ Z & ⟶ & aZ | ϵ \end{matrix}

Exercice 4.4 Le berger, le loup, la chèvre et le chou.

Tout le monde connait le problème du berger, de la chèvre, du chou et du loup. Le problème est le suivant:

Un berger décide de faire traverser une rivière à une chèvre, un chou et un loup. Malheureusement en son absence, le loup mangerait la chèvre, de même, la chèvre mangerait le chou.

• Le problème à résoudre pour le berger est de trouver un moyen de faire traverser tout ce petit monde et que tous les acteurs arrivent entier sur l’autre rive, avec comme restriction le fait que le berger ne peut prendre sur son embarcation qu’ un seul autre “passager”, sans quoi l’ embarcation coulerait.

• Les problèmes à résoudre pour vous sont les deux suivants:

1. Réaliser un automate à états finis qui résolve ce problème

dans le sens suivant: On considère l’alphabet {0, 1, 2, 3} où le symbole 0 signifie que le berger traverse seul, le symbole 1 qu’il traverse avec la chèvre, le symbole 2 qu’il traverse avec le loup et 3 qu’il traverse avec le chou. Un état rend compte de la position des différents acteurs sur une berge ou sur l’autre. L’état initial stipule que tous les acteurs sont sur la même rive. Un mot est une séquence de déplacements et un mot du langage doit conduire à un état où tous les acteurs sont sur la même rive (on peut faire plusieurs aller-retour).

2. Une fois l’automate réalisé, donner la grammaire régulière qui lui correspond.

Exercice 4.5 Donner une description explicative du langage engendré par la grammaire suivant: S → AB, A → a|aA|bAA|AAb|AbA, B → b|bB|aBB|BaB|BBa.

Exercice 4.6 Minimiser l’automate suivant:

Figure 1: Des états inutiles?.