Trouver/concocter une MT grammaire qui valide engendre L=\left\{ a^{n^2} | n\in \mathbb{N}\right\}.
pas sûr que c'était à rendre; j'ai modifié l'énoncé pendant ma réflexion (!) et trouvé (je crois) une MT (machine de Turing) qui vérifie L au lieu d'une grammaire qui l'engendre.
Une solution (qui n'est pas forcément unique) proposée par M. Schreck est la suivante, qui part du même principe que ma solution MT (cf. plus bas), c'est à dire que pour n > 0, n2 = (n-1)2 + 2*(n-1) + 1 . A partir de là, le raisonnement peut être :
S | → | US | DF | on produit d'abord Un D F pour un “n” quelconque, éventuellement “D F” tout court. |
UD | → | DIGa | Tant qu'il y a un U (forcément devant le D), l'U est transformé (consommé) et propage un traitement (“G”) vers la droite |
Ga | → | aG | le “G” cherche le “I” délimitant un groupe de a(s) à droite |
GI | → | IaaG | le “G” rajoute “a a” au début du groupe suivant |
GF | → | F | arrivé à la fin de la production le “G” disparaît |
DF | → | e | sans aucun “U” (cas de n=0) on rend une chaîne nulle |
DI | → | T | plus d'U, on démarre la mise en forme qui consiste en la suppression des D, I, et F (et T) pour ne laisser que les “a” |
Ta | → | aT | T saute chaque a |
TI | → | T | T supprime chaque I |
TF | → | e | T disparaît avec F lorsqu'il l'atteint |
Son fonctionnement set illustré par un petit exemple (que je saisis tel que dans mes notes d'abord :) pour un n 3 3
S | → | US → UUS → UUUS → UUUDF |
UUUDF | → | UUD I G a F |
UUD I G a F | → | UUD I a G F |
UUD I a G F | → | UUD I a F |
UUD I a F | → | UD I G a I a F |
UD I G a I a F | → | UD I a G I a F |
UD I a G I a F | → | UD I a I a a G a F |
UD I a I a a G a F | → | UD I a I a a a G F |
UD I a I a a a G F | → | UD I a I a a a F |
UD I a I a a a F | → | DI G a I a I a a a F |
DI G a I a I a a a F | → | DI a G I a I a a a F |
DI a G I a I a a a F | → | DI a I a a G a I a a a F |
DI a I a a G a I a a a F | → | DI a I a a a G I a a a F |
DI a I a a a G I a a a F | → | DI a I a a a I a a G a a a F |
DI a I a a a I a a G a a a F | → | DI a I a a a I a a a G a a F |
DI a I a a a I a a a G a a F | → | DI a I a a a I a a a a G a F |
DI a I a a a I a a a a G a F | → | DI a I a a a I a a a a a G F |
DI a I a a a I a a a a a G F | → | DI a I a a a I a a a a a F |
D I a I a a a I a a a a a F | → | T a I a a a I a a a a a F |
T a I a a a I a a a a a F | → | a T I a a a I a a a a a F |
a T I a a a I a a a a a F | → | a T a a a I a a a a a F |
… | ||
→ | a a a a T I a a a a a F | |
… | ||
→ | a a a a a a a a a T F | |
→ | a a a a a a a a a |
Puisque \left(n-1\right)^2= n^2 - 2 \times n + 1, on constate que n^2 - \left(n-1\right)^2 = n^2 - n^2 + 2\times n - 1=2n-1=2\left(n-1\right) + 1.
En effet, si l'on pense aux dessins de carrés, il est claire qu'à partir d'un carré n*n, un carré (n+1)*(n+1) n'est que le carré n*n plus une ligne de n+1 et une colonne de n+1 moins le coin où les deux (nouvelle ligne, nouvelle colonne) se répète.
1 | 2 | 3 | 4 | … |
---|---|---|---|---|
2 | 2 | 3 | 4 | … |
3 | 3 | 3 | 4 | … |
4 | 4 | 4 | 4 | … |
… |
La MT peut donc chercher à vérifier si le nombre de a
est 1, 1 + (2*1+1), 1+(2*1+1)+(2*2+1), ou \displaystyle \sum_{k=0}^n \left(1+2\times k\right) pour un nombre
n
quelconque. Il suffit de tester s'il n'y a pas de a
, il y a un seul a
ou, s'il y a plus, si le nombre total correspond à cette somme pour une valeur de n. Après le test pour 0 a
et 1 a
, on lance une itération tant qu'il reste des a
: on efface (2*k + 1) a
si on peut, puis on constate si c'est tout ce qu'il y en avait. Si oui, on accepte; si non, on augmente k:=k+1 et on poursuit une itération.