Easy proof for context-free languages being closed under cyclic shift

Problem Detail: 

The cyclic shift (also called rotation or conjugation) of a language $L$ is defined as $\{ yx \mid xy \in L \}$. According to wikipedia (and here) the context-free languages are closed under this operation, with references to papers from Oshiba and from Maslov. Is there an easy proof of this fact?

For regular languages the closure is discussed in this form as "Prove that regular languages are closed under the cycle operator".

Asked By : Hendrik Jan

Answered By : Yuval Filmus

You can try to use pushdown automata. Given a pushdown automaton for the original language, we construct one for the cyclic shift. The new automaton operates in two stages, corresponding to the $y$ and the $x$ part of the word $yx$ (where $xy$ is in the original language). In the first stage, whenever the automaton would like to pop a non-terminal $A$, it can instead push a non-terminal $A'$; the idea is that at the end of the first stage, the stack would contain, in reverse order, the symbols that are found in the stack after reading $x$ by the original automaton. In the second stage (the switch is non-deterministic), instead of pushing a non-terminal $A$, we are allowed to pop a non-terminal $A'$. If the original automaton can indeed generate the stack upon reading $x$, then the new one would be able to exactly pop the entire stack.

Edit: Here are some more details. Suppose we are given a PDA with alphabet $\Sigma$, set of states $Q$, set of accepting states $F$, non-terminals $\Gamma$, initial state $q_0$, and a set of allowable transitions. Each allowable transition is of the form $(q,a,A,q',\alpha)$, meaning that when in state $q$, upon reading $a \in A$ (or $a = \epsilon$, in which case it's a free transition), if the top-of-stack is $A \in \Gamma$ (or $A = \epsilon$, which means stack is empty), then the PDA can (it's a non-deterministic model) move to state $q'$, replacing $A$ with $\alpha \in \Gamma^*$.

The new PDA has a new non-terminal $A'$ for each $A \in \Gamma$. For every two states $q,q' \in Q$ and $A \in \Gamma \cup \{\epsilon\}$, there are two states $(q,q',1),(q,q',2,A)$. The starting states (the actual starting state is chosen non-deterministically among them via $\epsilon$-transitions) are $(q,q,1)$. For each transition $(q,a,A,q',\alpha)$ there are corresponding transitions $((q,q'',1),a,A,(q',q'',1),\alpha)$ and $((q,q'',2,B),a,A,(q',q'',2,B),\alpha)$. There are other transitions as well.

For each transition $(q,a,A,q',\alpha)$, there are transitions $((q,q'',1),a,B',(q',q'',1),B'A'\alpha)$, where $B \in \Gamma \cup \{\epsilon\}$ and $\epsilon' = \epsilon$. For every final state $q \in F$, there are transitions $((q,q'',1),\epsilon,A,(q_0,q'',2,\epsilon),A)$, where $A \in \Gamma \cup \{\epsilon\}$.

For every transition $(q,a,\epsilon,q',\alpha)$, there are transitions $((q,q'',2,A),a,B',(q',q'',2,A),B'\alpha)$, where $A \in \Gamma \cup \{\epsilon\}$. For every transition $(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'$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/7831