Einfacher Beweis dafür, dass kontextfreie Sprachen im zyklischen Wandel geschlossen werden

Die zyklische Verschiebung (auch Rotation oder Konjugation genannt ) einer Sprache $L$ ist definiert als $\{ yx \mid xy \in L \}$ . Laut Wikipedia (und hier ) sind die kontextfreien Sprachen im Rahmen dieser Operation geschlossen, mit Verweisen auf Artikel aus Oshiba und aus Maslow. Gibt es einen einfachen Beweis für diese Tatsache?

Für reguläre Sprachen wird der Abschluss in dieser Form als " Beweisen Sie, dass reguläre Sprachen unter dem Zyklusoperator geschlossen sind " erläutert .

Sie können versuchen, Pushdown-Automaten zu verwenden. Mit einem Pushdown-Automaten für die Originalsprache konstruieren wir einen für die zyklische Verschiebung. Der neue Automat arbeitet in zwei Stufen, die dem y- und dem x- Teil des Wortes y x entsprechen (wobei x y in der Originalsprache ist). In der ersten Stufe kann der Automat, wann immer er ein Nicht-Terminal A platzen lassen möchte , stattdessen ein Nicht-Terminal A ' drücken ; Die Idee ist, dass der Stapel am Ende der ersten Stufe in umgekehrter Reihenfolge die Symbole enthält, die nach dem Lesen von x im Stapel gefunden werden$y$$x$$yx$$xy$$A$$A'$$x$durch den ursprünglichen Automaten. In der zweiten Stufe (der Schalter ist nicht deterministisch) dürfen wir , anstatt ein Nicht-Terminal A zu drücken , ein Nicht-Terminal A 'platzen lassen . Wenn der ursprüngliche Automat tatsächlich den Stapel beim Lesen von x erzeugen kann , kann der neue den gesamten Stapel exakt platzen lassen.$A$$A'$$x$

Bearbeiten: Hier sind einige weitere Details. Angenommen, wir erhalten einen PDA mit dem Alphabet Σ , einer Menge von Zuständen Q , einer Menge von Akzeptanzzuständen F , Nichtterminals Γ , einem Anfangszustand q 0 und einer Menge zulässiger Übergänge. Jeder zulässige Übergang hat die Form ( q , a , A , q ' , α ) , was bedeutet, dass im Zustand q beim Lesen von a ∈ A (oder a = ϵ , in diesem Fall handelt es sich um einen freien Übergang) oben liegt -of-Stack ist A $\Sigma$$Q$$F$$\Gamma$$q_0$$(q,a,A,q',\alpha)$$q$$a \in A$$a = \epsilon$Γ (oder A = ε , was bedeutet Stapel leer ist), dannder PDA kann (es ist ein nicht-deterministisches Modell) zu bewegen Zustand q ' , Ersetzen A mit & agr; ∈ Γ * .$A \in \Gamma$$A = \epsilon$$q'$$A$$\alpha \in \Gamma^*$

Der neue PDA hat eine neue nicht-terminale A ' für jedes A ∈ & Ggr; . Für jeweils zwei Zustände q , q ' ∈ Q und A ∈ & Ggr; ∪ { ε } , gibt es zwei Zustände ( q , q ' , 1 ) , ( q , q ' , 2 , A ) . Die Startzustände (der tatsächliche Startzustand wird über ϵ- Übergänge nicht deterministisch unter ihnen gewählt ) sind $A'$$A \in \Gamma$$q,q' \in Q$$A \in \Gamma \cup \{\epsilon\}$$(q,q',1),(q,q',2,A)$$\epsilon$q , q , 1 ) . Für jeden Übergang ( q , a , A , q ' , α ) gibt es entsprechende Übergänge ( ( q , q " , 1 ) , a , A , ( q ' , q " , 1 ) , α ) und ( ( q , q " , 2 , $(q,q,1)$$(q,a,A,q',\alpha)$$((q,q'',1),a,A,(q',q'',1),\alpha)$) , a , A , ( q ' , q ' ' , 2 , B ) , α ) . Es gibt auch andere Übergänge.$((q,q'',2,B),a,A,(q',q'',2,B),\alpha)$

Für jeden Übergang ( q , a , A , q ' , α ) gibt es Übergänge ( ( q , q " , 1 ) , a , B ' , ( q ' , q " , 1 ) , B ' A ' α ). , wobei B ∈ & Ggr; ∪ { ε } , und ε '$(q,a,A,q',\alpha)$$((q,q'',1),a,B',(q',q'',1),B'A'\alpha)$$B \in \Gamma \cup \{\epsilon\}$ϵ . Für jeden Endzustand q ∈ F gibt es Übergänge ( ( q , q " , 1 ) , ε , A , ( q 0 , q " , 2 , ε ) , A ) , wobei A ∈ & Ggr; ∪ { ε } .$\epsilon' = \epsilon$$q \in F$$((q,q'',1),\epsilon,A,(q_0,q'',2,\epsilon),A)$$A \in \Gamma \cup \{\epsilon\}$

Für jeden Übergang ( q , a , ϵ , q ' , α ) gibt es Übergänge ( ( q , q " , 2 , A ) , a , B ' , ( q ' , q " , 2 , A ) , B ' α ) , wobei A ∈ & Ggr; ∪ { ε } . Für jeden Übergang$(q,a,\epsilon,q',\alpha)$$((q,q'',2,A),a,B',(q',q'',2,A),B'\alpha)$$A \in \Gamma \cup \{\epsilon\}$$(q,a,\epsilon,q',A)$, there are transitions $((q,q'',2,B),a,A',(q',q'',2,A),\epsilon)$, where $B \in \Gamma \cup \{\epsilon\}$. For every transition $(q,a,A,q',B)$, there are "generalized transitions" $((q,q'',2,C),a,B'A,(q,q'',2,C),\epsilon)$; these are implemented as a sequence of two transitions through an intermediate new state. Transitions $(q,a,\epsilon,q',\alpha)$ with $|\alpha| \geq 2$ are handled similarly. For every transition $(q,a,A,q',A)$, there are transitions $((q,q'',2,A),a,B,(q',q'',2,A),B)$, where $B \in \Gamma' \cup \{\epsilon\}$. Transitions $(q,a,A,q',A\alpha)$ are handled similarly. Finally, there is a sole final state $f$, and transitions $((q,q,2,A),\epsilon,\epsilon,f,\epsilon)$.

(There might be a few transitions that I missed, and some of the details that I'm omitting are somewhat messy.)

Recall we're trying to accept a word $yx$, where $xy$ is accepted by the original PDA. A state $(q,q',1)$ means that we're at stage 1, at state $q$, and the original PDA is at state $q'$ after reading $x$. A state $(q,q',2,A)$ is similar, where $A$ corresponds to the last $A'$ that was popped. At stage 1, we are allowed to push $A'$ instead of popping $A$. We do that for each non-terminal that is produced while processing $x$, but only popped while processing $y$. At stage 2, we are allowed to pop $A'$ instead of pushing $A$. If we do this, then we have to remember that the top-of-stock is really $A$; this only applies when there are no "temporary" things on the stack, which in the simulated PDA is the same as the top-of-stack being $\epsilon$ or of the form $B'$.

Here is a simple example. Consider an automaton for $x^n y^n$ that pushes $A$ for each $x$, and pops $A$ for each $y$. The new automaton accepts words of two forms: $y^k x^n y^{n-k}$ and $x^k y^n x^{n-k}$. For words of the first form, stage 1 consists of pushing $k$ times $A'$, stage 2 consists of popping $k$ times $A'$, pushing $n-k$ times $A$, and popping $n-k$ times $A$. For words of the second form, we first push $k$ times $A$, then pop $k$ times $A$, push $n-k$ times $A'$, transition to stage 2, and pop $n-k$ times $A'$.

Here is a more complicated example, for the language of balanced parentheses of various types ("()","[]","<>") such that the immediate descendants of each type of parentheses must belong to a different type. For example, "([]<>)" is OK but "()" is wrong. For each "(", we push $A$ if the top-of-stack isn't $A$, for each ")", we pop $A$. Similarly $B$,$C$ are associated with "[]" and "<>". Here is how we accept the word ">)([()]<". We consume ">)", pushing $C'A'$, and transition to stage 2. We consume "(", popping $A'$ and remembering the top-of-stack $A$. We consume "[()]" , pushing and popping $BA$; when pushing $B$, we are aware that the "real" top-of-stack is $A$, and so square brackets are allowed (we wouldn't be fooled by ">)(()<"); when pushing $A$, since the top-of-stack is $B$ (which is not $\epsilon$ or of the form $X'$), then we know that $B$ is also the "real" top-of-stack, and so round parentheses are allowed (even though the shadow top-of-stack is $A$). Finally, we consume "<" and pop $C'$.

Consider Greibach normal form. To construct a shifted language you only need to change productions $S \to \alpha A_1 \dots A_n$ to $S \to A_1\dots A_n \alpha$ and add a new non-terminal $S'$ that behaves like $S$ used to, in case some some production referenced $S$.

It turned out to be a good idea to check the old Hopcroft and Ullman classic Introduction to Automata Theory (1979). Closure under cycle is Exercise 6.4c and is marked S**. The double stars mean it is one of the most difficult problems (in the book). Fortunately the S indicates it is one of the selected problems with a solution.

The solution is as follows. Take a CFG in Chomsky normal form. Consider any derivation tree and basically turn it upside down. Consider a path $S=X_1, X_2, \dots , X_n$ in the original tree. To the left the tree has contributions $x_1, x_2, \dots, x_n$ to the right $y_1, y_2, \dots, y_n$, meaning the string derived equals $x_1 x_2 \dots x_n y_n \dots y_2 y_1$. (Actually as the grammar is CNF when the path continues left, the contribution will be to the right and the corresponding $x_i$ is empty, etc.)

The tree upside down has a path $S', \hat X_n, \dots \hat X_2, \hat X_1$ with contributions $y_n, \dots, y_2 y_1$ to the left and $x_n, \dots, x_2 x_1$ to the right, so the result is a derivation for $y_n \dots y_2 y_1 x_1 x_2 \dots x_n$. As required.

Full details of the construction are given in the book.

Note how this reminds of the (accepted) solution by Yuval. The nonterminals that are pushed instead of popped are in the opposite order on the stack. Quite similar to upside down in the tree.