===== 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 FIXME:) pour un n 3 3 | S | -> | US -> UUS -> UUUS -> UUUDF | | UU__UD__F | -> | UU__D I G a__ F | | UUD I __G a__ F | -> | UUD I __a G__ F | | UUD I a __G F__ | -> | UUD I a __F__ | | U__UD__ I a F | -> | U__D 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.