---

[Entre cochets, sont ajoutés des commentaires. Ces commentaires ne devaient pas obligatoirement figurer sur la copie. Le barême est indiqués. Il fallait bien lire le sujet sans se lancer tête baissée sur la question I]

---

Ce qui se simplifie en A3 :

[Méthode possible pour la simplification : les équations des langages des états 3, 4 et 5 pour A2. Est-ce que L3 = (a+b)* comme on pourrait en avoir l'intuition en comparant A1 et A2 ?]

Par les équations à partir de A2 :

L3 = aL4 + bL3 + epsilon
L4 = aL4 + bL5 + epsilon
L5 = aL4 + bL3 + epsilon

On observe que L5 = L3.
Donc L4 = aL4 + bL3 + epsilon
En résolvant : L4 = a*( bL3 + epsilon)
Donc L3 = a a*(bL3 + epsilon) + bL3 + epsilon
L3 = (a a*b +b)L3 + aa* + epsilon
L3 = a*bL3 + a*
En résolvant : L3 = (a*b)*a* = (a+b)*

I.2. (sur 2)

On peut, toujours par la méthode des équations, en déduire depuis A3 l’ERNA demandée :

L0= bL0 + aL1
L1 = aL1 + bL2
L2 = aL1 + bL3
L3 = (a+b)L3 + epsilon

L3 = (a+b)*
L2 = aL1 + b(a+b)*
L1 = aL1 + baL1 + bb(a+b)*
Donc L1 = (a + ba)L1 + bb(a+b)*
En résolvant : L1 = (a + ba)* bb(a+b)*
Donc L0 = bL0 + a(a + ba)* bb(a+b)*
En résolvant : L0 = b* a(a + ba)* bb(a+b)*

[On s’apperçoit, pour peu qu’on ait lu le sujet en entier avant de commencer, qu’il s’agit de l’ER donnée au III.2 avec a et b échangés.
]

I.3. (sur 2)

[On pouvait trouver en faisant L13 = b* a(a + ba + bba)*bbb(a+b)* et par analogie. Mais surtout en comprenant que l’expression régulière pour n = 2 est surtout égale à :

L1₂ = b* a(a + ba)* bb(a+b)* = b*(a + ba)* abb(a+b)*
Car : a(a + ba)* = a((epsilon + b)a)* = (a(epsilon + b))*a = (a+ab)*a
Avec L1₂ = b*(a + ba)* abb(a+b)* et
L1_n = b* (a + ba + bba + bbba+ … bn-1a)* abn (a+b)*


On voit mieux que l’ER se compose de trois morceaux : le abⁿ , avant abⁿ et après abⁿ. Une fois que l’on a fait le abⁿ obligatoire (il en faut au moins 1), on peut faire se que l’on veut donc (a+b)*. Avant d’avoir fait le abn obligatoire, on peut tout faire sauf un abn sinon l’ER serait ambiguë. Ce premier morceau correspond bien à : b* (a + ba + bba + bbba+ … b^n-1a)*
]

L1₁ = b*(a)* ab(a+b)*
L1₂ = b*(a + ba)* abb(a+b)*
L1₃ = b*(a + ba + bba)* abbb(a+b)*

[et d’ailleurs L1₀ = b*a(a+b)*
]

Question II (sur 8)

II.1. (sur 3)

Grammaire de type 3 (mais pas epsilon libre)

Comme elle est de type 3, on peut donc faire son automate, on y verra sûrement plus clair :

Posons les équations :

LA = (a+b)LA + aLB
LB = bLC
LC = bLD
LD = bLE
LE = (a+b)LE + epsilon + (a+b)LA

LE = (a+b)*(epsilon + (a+b)LA)
LD = b(a+b)*(epsilon + (a+b)LA)
LC = bb(a+b)*(epsilon + (a+b)LA)
LB = bbb(a+b)*(epsilon + (a+b)LA)
LA = (a+b)LA + abbb(a+b)*(epsilon + (a+b)LA)
Soit LA = (a+b + abbb(a+b)*(a+b))LA + abbb(a+b)*
En résolvant : LA = (a+b + abbb(a+b)*(a+b))*abbb(a+b)*

On peut simplifier en remarquant que (a+b) est inclus dans (a+b + abbb(a+b)*(a+b)) donc (a+b)* est inclus dans (a+b + abbb(a+b)*(a+b))*
Or tout est L est inclus dans V* = (a+b)*
Donc (a+b)* = (a+b + abbb(a+b)*(a+b))*

Donc LA = (a+b)*abbb(a+b)*

[on pouvait bien sûr aussi répondre L =b*(a + ba + bba)* abbb(a+b)* = L1₃
]

II.2. (sur 2)

Comme L = L1₃, on considère maintenant l’automate déterministe correspondant à L1₃ , soit :

Ce qui donne comme grammaire G’ non-ambigüe (mais pas epsilon libre) :

A --> bA | aB
B --> aB | bC
C --> aB | bD
D --> aB | bE
E --> aE | bE | epsilon

[On pouvait aussi partir partir de l'automate non-déterministe et trouver:

A --> aA | bA | aB
B --> bC
C --> bD
D --> dE
E --> aE | bE | epsilon


Toutefois dans l'énoncé, on ne demandait pas qu'elle soit de type 3, on peut donc en trouver d'autres.]

II.3. (sur 3)

L’automate non déterministe de L = (a+b)*abbb(a+b)* est :

Cherchons le langage mirroir de L = L1₃. Pour cela on produit l’automate mirroir (en inversant le sens des transitions - et en échangeant états final et initial - comme décrit dans le support de cours)

On obtient l’automate correspondant à l’ER : (a+b)*bbba(a+b)*.

Si on fait l’union des ER de L et de Mirroir(L), on obtient :
L2 = (a+b)*abbb(a+b)* + (a+b)*bbba(a+b)*

On peut aussi passer par l’automate union entre A_L2 et Mirroir(A_L2) :

[On peut " lire " l’ER de ce dernier automate :
(a+b)*abbb(a+b)* + (a+b)*bbba(a+b)* = (a+b)*(abbb + bbba)(a+b)*
On pouvait aussi simplement trouver cet automate directement à partir de l'ER:
(a+b)*(abbb+bbba)(a+b)*]

On trouve la grammaire directement par traduction de l’automate. Ce qui donne comme grammaire G2 (pas epsilon libre) :

S  --> aS | bS | aA | bA’
A  --> bB
A’ --> bB’
B  --> bC
B’ --> bC’
C  --> bF
C’ --> aF
F  --> aF | bF | epsilon


[Bien que cela ne soit pas demandé, on peut obtenir la version epsilon-libre – une vraie type 3 – de cette grammaire :

S  --> aS | bS | aA | bA’
A  --> bB
A’ --> bB’
B  --> bC
B’ --> bC’
C  --> bF | b
C’ --> aF | a
F  --> aF | bF | a | b
]

[Bien que cela soit bien plus long et non demandé, on pouvait aussi utiliser la version déterministe de L2. Cette option bien que possible est périlleuse.]

Question III (sur 8)

III.1. (sur 3)

Pour L3_n avec n = 2, on a l’automate :

Ce qui est exactement l’automate du langage L1_n avec n = 2 où a et b ont été échangés.
Si on échange a et b dans l’ER suivante : b* a(a + ba)* bb(a+b)*, on obtient :

[On peut retrouver l’expression régulière à nouveau par la méthode des équations, mais ce travail est exactement celui de la question I.2 (en échangeant a et b)
]

III.2. (sur 3)

Il faut calculer l’intersection entre L1_n avec n = 1 et L3_n avec n = 1. C’est-à-dire entre a* bb* a(a+b)* et b* aa* b(a+b)*. Ou encore l’intersection entre les deux automates suivants :

L’état 5 est final car 2 et 2’ sont finaux.

Clairement, il s’agit du language dont les mots contiennent à la fois la sous-chaîne " ab " et la sous-chaîne " ba ".

On peut trouver l’expression régulière par la méthode des équations.

L0 = aL1 + bL2
L1 = aL1 + bL3
L2 = bL2 + aL4
L3 = bL3 + aL5
L4 = aL4 + bL5
L5 = (a+b)L5 + epsilon = (a+b)*

Donc L4 = a*b(a+b)* et L3 = b*a(a+b)*
Donc L2 = b*aa*b(a+b)* et L1 = a*b b*a(a+b)*
Donc L0 = aa*bb*a(a+b)* + bb*aa*b(a+b)*
En factorisant L0 = (aa*bb*a+ bb*aa*b)(a+b)*

Tous les mots donnés en exemple en I sauf " abb " appartiennent à L4_1-1. " abb " ne contient pas " ba ". Tous les autres contiennent à la fois " ab " et " ba ".

III.3. (sur 2) On peut déduire directement la machine de Turing de l’automate ci-dessus.

Pas de prologue (comme pour toutes les machines de Turing issues d'automates].

Les épilogues : Comme d'habitude - on utilise les états qr pour la situation de réussite et qe pour celle d’échec.
A partir de qr on se placera sur le 0 le plus àdroite si on est pas déjà sur un 0 et on repartira à gauche en effaçant tout jusqu’au premier 0. En se mettra sur la case de départ en se décalant d’un cran à droite et en ecrivant 1 (le mot appartient à L).

Idem pour qe mais on n’écrit rien (ou alors un 0) à la fin.

Epilogue d’échec :

(qe, a, qe, D)
(qe, b, qe, D)
(qe, 0, qe1, G)

(qe1, a, qe2, 0)
(qe1, b, qe2, 0)
(qe1, 0, qe3, D)

(qe2, 0, qe1, G)

(qe3, 0, qf, 0)

Epilogue de réussite:

(qr, a, qr, D)
(qr, b, qr, D)
(qr, 0, qr1, G)

(qr1, a, qr2, 0)
(qr1, b, qr2, 0)
(qr1, 0, qr3, D)

(qr2, 0, qr1, G)

(qr3, 0, qf, 1)

Corps du programme :

(q0, a, q1, D)
(q0, b, q2, D)
(q0, 0, qe, 0)

(q1, a, q1, D)
(q1, b, q3, D)
(q1, 0, qe, 0)

(q2, a, q4, D)
(q2, b, q2, D)
(q2, 0, qe, 0)

(q3, a, q5, D)
(q3, b, q3, D)
(q3, 0, qe, 0)

(q4, a, q4, D)
(q4, b, q5, D)
(q4, 0, qe, 0)

(q5, a, q5, D)
(q5, b, q5, D)
(q5, 0, qr, 0)


[la création de la machine de Turing n’était ni longue ni difficile – à condition d’avoir trouvé l’automate bien sûr.
Les commentaires sur les transitions de la machine de Turing sont inutiles dans la mesure ou il s’agit de la traduction directe de l’automate.

Il n’était pas besoin d’écrire les épilogues s’ils étaient définis correctement.
]

[Commentaire général :
le sujet était de difficulté moyenne et n’était pas trop long si on repérait astucieusement les symétries et les rapports entre les questions. C'est pour qu'il est recommandé de bien lire l'ensemble du sujet avant de commencer.

La simplification de la question I.1 devait être faite avec soin en reperant que L5=L2.
La question I.2 demandait simplement l'automate déterministe de la question d'avant, et la méthodes des équations (facile) ou de réduction d'automate (dur). La question I.3 demandait un peu d'intuition (mais aucune justification n'était de demandée). II.1 etait facile en passant par l'automate, problématique sinon. Le II.2 demandait la déterminisation de l'automate de G et se simplifiait le plus facilement par la double inclusion sinon risquait d'être difficile. Pour II.3 surtout ne pas passer par les automates non-déterministes. III.2 était facile malgré les apparences. III.3 n'était faisable que si on avait fait III.2 (mais on pouvait toujours décrire le principe, histoire de sauver les meubles)

En plus c'était noté sur 24 !!!]

Fait le 20/01/2000 - Mathieu Lafourcade