Enoncé
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.
Corrigé
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 :
- on se donne “n”, un entier exprimé en unaire en entrée et une zone de retour délimitée par “D …F” initialement.
- sans un seul U (pour zéro donc) on devra rendre un résultat nul, d'où “D F → e”.
- on bouclera pour k= 1 à n, rajoutant “2*(k-1) + 1” à chaque passage. On comptera le nombre de passages déjà effectués en écrivant un “I” une fois par passage.
- on ajoute un “I” et un “a” : “UD → D I G a” (ou “UD → D I a G”?)
- pour chaque “I” déjà présent, on rajoute (insère) “a a”, soit 2*(k-1) fois “a” au total : “G I → I a a G”. Ainsi on produira successivement
- D a F
- D a I a a a F
- D a I a a a I a a a a a F
- etc.
- lorsqu'il n'y a plus de “U”, on met on forme le résultat, supprimant les délimiteurs. Nos délimiteurs et autres utilitaires seront :
- “D” et “F” pour la zone de résultat (production)
- “I” pour délimiter le “a” (futur groupe d'a éventuel) ajouté en t^te de production par un passage dans la boucle
- “G” pour chercher les “I” et insérer “a a”, puis disparaître en fin de production
- “T” pour balayer et nettoyer.
| 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 |
Ma Solution "MT"
Principes
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.
- if lecture==' ' then return “n”; puisque a^0 \neq a
- else right(1);
- if lecture==' ' then return “y”; puisque a^{1^2} = a
- else write(' '); R_\sqcup €R1R€L_€
- S1: L_\sqcup R
- if lecture=='€' then return “n”;
- else [lecture=='a'] \sqcup R_€ R_{\bar{\sqcup}}
- if lecture==1 \sqcup goto S1.
- S2: if lecture==€ : L
- if lecture==' ' write('1'); goto S2.
- lecture==€ : goto S3.
- S3: L_\sqcup R
- if lecture=='€' then return “n”;
- else [lecture=='a'] \sqcup R_€ R_{\bar{\sqcup}}
- if lecture==1 \sqcup goto S3.
- S4: if lecture==€ : L
- if lecture==' ' write('1'); goto S4.
- lecture==€ : goto S5.
- S5: L_\sqcup R
- if lecture!='a' return “n”.
- else R
- if lecture==€ return “y”
- else [lecture==a] L \sqcup R_€ R_€ 1 R € L_€ ; goto S3.