Preuve facile pour les langues sans contexte fermées par changement cyclique

11

Le décalage cyclique (également appelé rotation ou conjugaison ) d'un langage est défini comme . Selon wikipedia (et ici ), les langages sans contexte sont fermés dans le cadre de cette opération, avec des références aux articles d'Oshiba et de Maslov. Y a-t-il une preuve facile de ce fait?L { y x x y L }L{yxxyL}

Pour les langues régulières, la fermeture est discutée sous cette forme comme " Prouver que les langues régulières sont fermées sous l'opérateur de cycle ".

Hendrik Jan
la source

Réponses:

5

Vous pouvez essayer d'utiliser des automates pushdown. Étant donné un automate de refoulement pour la langue d'origine, nous en construisons un pour le décalage cyclique. Le nouvel automate fonctionne en deux étapes, correspondant à la partie et du mot (où est dans la langue d'origine). Dans la première étape, chaque fois que l'automate souhaite pop un non-terminal A , celle - ci peut pousser un non-terminal A » ; l'idée est qu'à la fin de la première étape, la pile contiendrait, dans l'ordre inverse, les symboles qui se trouvent dans la pile après lecture de x par l'automate d'origine. Dans la deuxième étape (l'interrupteur est non-déterministe), au lieu de pousser un non-terminal Ay x y x x y A A x AyxyxxyAAxA, Nous sommes autorisés à sauter un non-terminal A A . Si l'automate d'origine peut en effet générer la pile lors de la lecture de Xx , alors le nouveau pourrait exactement éclater la pile entière.

Edit: Voici quelques détails supplémentaires. Supposons que l'on nous donne un PDA avec l'alphabet , un ensemble d'états , un ensemble d'états accepteurs , des non-terminaux , un état initial et un ensemble de transitions autorisées. Chaque transition autorisée est de la forme , ce qui signifie que lorsqu'elle est dans l'état , à la lecture d' (ou , auquel cas c'est une transition libre), si le haut de la pile est (ou , ce qui signifie que la pile est vide), alors le PDA peut (c'est un modèle non déterministe) passer à l'état , en remplaçantΣ Q F Γ q 0 ( q , a , A , q , α ) q a A a = ϵ A Γ A = ϵ q A α Γ ΣQFΓq0(q,a,A,q,α)qaAa=ϵAΓA=ϵqA avec .αΓ

Le nouveau PDA a un nouveau non terminal pour chaque . Pour tous les deux états et , il y a deux états . Les états de départ (l'état de départ réel est choisi de manière non déterministe parmi eux via -transitions) sont . Pour chaque transition il y a des transitions correspondantes et . Il existe également d'autres transitions.A A Γ q , q Q A Γ { ϵ } ( q , q , 1 ) , ( q , q , 2 , A ) ϵ ( q , q , 1 ) ( q , a , A , q , α ) ( ( q ,AAΓq,qQAΓ{ϵ}(q,q,1),(q,q,2,A)ϵ(q,q,1)(q,a,A,q,α)q , 1 ) , a , A , ( q , q , 1 ) , α ) ( ( q , q , 2 , B ) , a , A , ( q , q , 2 , B ) , α )((q,q′′,1),a,A,(q,q′′,1),α)((q,q′′,2,B),a,A,(q,q′′,2,B),α)

Pour chaque transition , il y a des transitions , où et . Pour chaque état final , il y a des transitions , où .( q , a , A , q , α ) ( ( q , q , 1 ) , a , B , ( q , q , 1 ) , B A α ) B Γ { ϵ } ϵ = ϵ q F ( ( q ,(q,a,A,q,α)((q,q′′,1),a,B,(q,q′′,1),BAα)BΓ{ϵ}ϵ=ϵqFq , 1 ) , ϵ , A , ( q 0 , q , 2 , ϵ ) , A ) A Γ { ϵ }((q,q′′,1),ϵ,A,(q0,q′′,2,ϵ),A)AΓ{ϵ}

Pour chaque transition , il y a des transitions , où . Pour chaque transition , il y a des transitions , où . Pour chaque transition , il existe des "transitions généralisées" ; ceux-ci sont implémentés comme une séquence de deux transitions à travers un nouvel état intermédiaire. Transitions\ alpha) avec( q , a , ϵ , q , α ) ( ( q , q , 2 , A ) , a , B , ( q , q , 2 , A ) , B α ) A Γ { ϵ } ( q , a , ϵ , q (q,a,ϵ,q,α)((q,q′′,2,A),a,B,(q,q′′,2,A),Bα)AΓ{ϵ}, A ) ( ( q , q , 2 , B ) , a , A , ( q , q , 2 , A ) , ϵ ) B Γ { ϵ } ( q , a , A , q , B ) ( ( q , q , 2(q,a,ϵ,q,A)((q,q′′,2,B),a,A,(q,q′′,2,A),ϵ)BΓ{ϵ}(q,a,A,q,B),C),a,BA,(q,q,2,C),ϵ)((q,q′′,2,C),a,BA,(q,q′′,2,C),ϵ)(q,a,ϵ,q,α)(q,a,ϵ,q,α)|α|2|α|2sont traités de la même manière. Pour chaque transition , il y a des transitions , où . Les transitions sont gérées de la même manière. Enfin, il existe un seul état final , et des transitions .(q,a,A,q,A)(q,a,A,q,A)((q,q,2,A),a,B,(q,q,2,A),B)((q,q′′,2,A),a,B,(q,q′′,2,A),B)BΓ{ϵ}BΓ{ϵ}(q,a,A,q,Aα)(q,a,A,q,Aα)ff((q,q,2,A),ϵ,ϵ,f,ϵ)((q,q,2,A),ϵ,ϵ,f,ϵ)

(Il peut y avoir quelques transitions que j'ai manquées, et certains des détails que j'omets sont quelque peu désordonnés.)

Rappelons que nous essayons d'accepter un mot , où est accepté par le PDA d'origine. Un état signifie que nous sommes à l'étape 1, à l'état , et le PDA d'origine est à l'état après avoir lu . Un état est similaire, où correspond au dernier qui a été sauté. À l' étape 1, nous sommes autorisés à pousser au lieu de sauter . Nous le faisons pour chaque non-terminal qui est produit lors du traitement de , mais uniquement surgi lors du traitement de . À l'étape 2, nous sommes autorisés à faire éclateryxyxxyxy(q,q,1)(q,q,1)qqqqxx(q,q,2,A)(q,q,2,A)AAAAAAAAxxyyAAau lieu de pousser . Si nous faisons cela, alors nous devons nous rappeler que le haut de stock est vraiment ; cela ne s'applique que lorsqu'il n'y a pas de choses "temporaires" sur la pile, ce qui dans le PDA simulé est le même que le haut de la pile étant ou de la forme .AAAAϵϵBB

Voici un exemple simple. Considérons un automate pour qui pousse pour chaque et fait apparaître pour chaque . Le nouvel automate accepte les mots de deux formes: et . Pour les mots de la première forme, étape 1 consiste à pousser fois«étape 2 consiste à éclater fois , poussant fois et éclater fois . Pour les mots de la deuxième forme, nous poussons d'abord foisxnynxnynAAxxAAyyykxnynkykxnynkxkynxnkxkynxnkkkAAkkAAnknkAAnknkAAkkAA, puis pop fois , poussez fois , passez à l'étape 2 et pop fois .kkAAnknkAAnknkAA

Voici un exemple plus compliqué, pour le langage des parenthèses équilibrées de différents types ("()", "[]", "<>") de sorte que les descendants immédiats de chaque type de parenthèses doivent appartenir à un type différent. Par exemple, "([] <>)" est OK mais "()" est faux. Pour chaque « ( », nous poussons si le haut de la pile n'est pas , pour chaque « ) », nous pop . De même, , sont associés à "[]" et "<>". Voici comment nous acceptons le mot ">) ([()] <". Nous consommons ">)", en poussant et en passant à l'étape 2. Nous consommons "(", poppinget rappelant le haut de la pile . Nous consommons "[()]", poussant et éclatant ; en poussantAA AAAABBCCCACAAAAABABAB , nous savons que le "vrai" sommet de la pile est , et les crochets sont donc autorisés (nous ne serions pas dupes de ">) (() <"); en poussant , puisque le haut de la pile est (qui n'est pas ou de la forme ), alors nous savons que est aussi le "vrai" haut de la pile, et donc les parenthèses rondes sont autorisées (même si le sommet de la pile de l'ombre est ). Enfin, nous consommons "<" et pop .AABϵXBAC

Yuval Filmus
la source
Désolé, j'ai du mal à comprendre - pouvez-vous expliquer davantage? Où commence l'automate et quelles sont ses transitions? Et le passage de se produit-il pour chaque symbole de pile? Merci! AA
Usul
Suggestion très intéressante. Merci. Je vais le mâcher un peu pour le laisser pénétrer.
Hendrik
@usul, vous devrez remplir les détails vous-même. Le commutateur (dans la première étape) devrait se produire lorsque l'automate "veut" faire éclater mais ne peut pas, et à la place il pousse . Vous pouvez le considérer comme un mouvement non déterministe. AAAA
Yuval Filmus
@Yuval: désolé mais je ne peux pas y arriver. Si je comprends bien votre idée, le nouvel automate commence par simuler la partie , en changeant les pops et les pushs. Générez ensuite sur la pile, où l'automate d'origine commence par lors de la lecture de . Qu'est-ce que l'original commence en poussant? Ensuite, l'automate nwe doit sortir de la pile vide. Je pense toujours que votre intuition en vaut la peine, mais certains soins supplémentaires semblent nécessaires. yααy
Hendrik Jan
@Hendrik, je suis désolé, mais je ne peux pas suivre votre contre-exemple. À quel moment pensez-vous que le nouvel automate doit sortir de la pile vide?
Yuval Filmus
4

Considérez la forme normale de Greibach . Pour construire une langue déplacé il vous suffit de productions de changement S α A 1 ... A n à S A 1 ... A n α et ajouter un nouveau non-terminal S ' qui se comporte comme S utilisés pour, dans le cas où une partie de la production fait référence S .

Karolis Juodelė
la source
Merci, mais c'est décalé par une seule lettre. Je m'intéresse à la rotation générale, par un nombre arbitraire de lettres.
Hendrik Jan
3
@HendrikJan, Eh bien, si le décalage 1 ( L ) est sans contexte, donc le décalage n ( L ) = décalage 1 ( décalage 1 ( ( L ) ) sera sûrement également sans contexte. Vous pouvez construire une grammaire pour cela en en appliquant la méthode que j'ai suggérée n fois. Vous pouvez également construire directement la grammaire shift n ( L ) , en "aplatissant" la grammaire donnée. Par exemple si n = 2 et que la grammaire a des productions Sα A B et A β C , vous ajouteriez une production S α β C B et la tourneriez. Bien sûr, la taille de votre grammaire peut augmenter très rapidement.
Karolis Juodelė
1
Pour n fixe, vous avez raison. Mais ici n est fixe ni borné. Par exemple, si L = { a n b nn 0 } alors nous obtenons { a k b n a k + = n } { b k a n b k + = n } .
Hendrik Jan
@HendrikJan, je vois. J'ai supposé à tort que la question portait sur un changement fini. Je reconsidérerai ma réponse ...
Karolis Juodelė
4

Il s'est avéré être une bonne idée de vérifier l'ancien classique Introduction à la théorie des automates de Hopcroft et Ullman (1979). La fermeture sous cycle est l'exercice 6.4c et est marquée S **. Les doubles étoiles signifient que c'est l'un des problèmes les plus difficiles (dans le livre). Heureusement, le S indique que c'est l'un des problèmes sélectionnés avec une solution.

La solution est la suivante. Prenez un CFG sous forme normale de Chomsky. Considérez n'importe quel arbre de dérivation et tournez-le essentiellement à l'envers. Considérons un chemin S = X 1 , X 2 , , X n dans l'arbre d'origine. À gauche, l'arbre a les contributions x 1 , x 2 , , x n à droite y 1 , y 2 , , y n , ce qui signifie que la chaîne dérivée est égale à x 1 x 2x ny ny 2 y 1 . (En fait, comme la grammaire est CNF lorsque le chemin continue à gauche, la contribution sera à droite et le x i correspondantest vide, etc.)

L'arbre a la tête en bas d' un chemin S ' , X n , ... X 2 , X 1 avec des contributions y n , ... , y 2 y 1 vers la gauche et x n , ... , x 2 x 1 vers la droite, le résultat est donc une dérivation pour y ny 2 y 1 x 1 x 2x n . Comme demandé.

Tous les détails de la construction sont donnés dans le livre.

Notez comment cela rappelle la solution (acceptée) de Yuval. Les non terminaux qui sont poussés au lieu de sauter sont dans l'ordre inverse sur la pile. Assez semblable à l'envers dans l'arbre.

Hendrik Jan
la source