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

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$$\{ yx \mid xy \in L \}$

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 ".

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 $y$$x$$yx$$xy$$A$$A'$$x$$A$, Nous sommes autorisés à sauter un non-terminal $A'$ . Si l'automate d'origine peut en effet générer la pile lors de la lecture de $x$ , 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 α ∈ Γ $\Sigma$$Q$$F$$\Gamma$$q_0$$(q,a,A,q',\alpha)$$q$$a \in A$$a = \epsilon$$A \in \Gamma$$A = \epsilon$$q'$$A$ avec .$\alpha \in \Gamma^*$

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 $A'$$A \in \Gamma$$q,q' \in Q$$A \in \Gamma \cup \{\epsilon\}$$(q,q',1),(q,q',2,A)$$\epsilon$$(q,q,1)$$(q,a,A,q',\alpha)$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),\alpha)$$((q,q'',2,B),a,A,(q',q'',2,B),\alpha)$

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',\alpha)$$((q,q'',1),a,B',(q',q'',1),B'A'\alpha)$$B \in \Gamma \cup \{\epsilon\}$$\epsilon' = \epsilon$$q \in F$q ″ , 1 ) , ϵ , A , ( q 0 , q ″ , 2 , ϵ ) , A ) A ∈ Γ ∪ { ϵ $((q,q'',1),\epsilon,A,(q_0,q'',2,\epsilon),A)$$A \in \Gamma \cup \{\epsilon\}$

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,\epsilon,q',\alpha)$$((q,q'',2,A),a,B',(q',q'',2,A),B'\alpha)$$A \in \Gamma \cup \{\epsilon\}$, A ) ( ( q , q ″ , 2 , B ) , a , A ′ , ( q ′ , q ″ , 2 , A ) , ϵ ) B ∈ Γ ∪ { ϵ } ( q , a , A , q ′ , B ) ( ( q , q ″ , $(q,a,\epsilon,q',A)$$((q,q'',2,B),a,A',(q',q'',2,A),\epsilon)$$B \in \Gamma \cup \{\epsilon\}$$(q,a,A,q',B)$$((q,q'',2,C),a,B'A,(q,q'',2,C),\epsilon)$$(q,a,\epsilon,q',\alpha)$$|\alpha| \geq 2$sont 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,q'',2,A),a,B,(q',q'',2,A),B)$$B \in \Gamma' \cup \{\epsilon\}$$(q,a,A,q',A\alpha)$$f$$((q,q,2,A),\epsilon,\epsilon,f,\epsilon)$

(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 éclater$yx$$xy$$(q,q',1)$$q$$q'$$x$$(q,q',2,A)$$A$$A'$$A'$$A$$x$$y$$A'$au 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 .$A$$A$$\epsilon$$B'$

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 fois$x^n y^n$$A$$x$$A$$y$$y^k x^n y^{n-k}$$x^k y^n x^{n-k}$$k$$A'$$k$$A'$$n-k$$A$$n-k$$A$$k$$A$, puis pop fois , poussez fois , passez à l'étape 2 et pop fois .$k$$A$$n-k$$A'$$n-k$$A'$

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 poussant$A$ $A$$A$$B$$C$$C'A'$$A'$$A$$BA$$B$ , 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 .$A$$A$$B$$\epsilon$$X'$$B$$A$$C'$

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 .$S \to \alpha A_1 \dots A_n$$S \to A_1\dots A_n \alpha$$S'$$S$$S$

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 2 … x $S=X_1, X_2, \dots , X_n$$x_1, x_2, \dots, x_n$$y_1, y_2, \dots, y_n$y n … y 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.)$x_1 x_2 \dots x_n y_n \dots y_2 y_1$$x_i$

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 n … y 2 y 1 x 1 x 2 … x n . Comme demandé.$S', \hat X_n, \dots \hat X_2, \hat X_1$$y_n, \dots, y_2 y_1$$x_n, \dots, x_2 x_1$$y_n \dots y_2 y_1 x_1 x_2 \dots x_n$

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.