Prova fácil de fechamento de idiomas sem contexto sob mudança cíclica

O deslocamento cíclico (também chamado de rotação ou conjugação ) de uma linguagem é definido como . De acordo com a wikipedia (e aqui ), as linguagens sem contexto são fechadas nesta operação, com referências a artigos de Oshiba e Maslov. Existe uma prova fácil desse fato?$L$$\{ yx \mid xy \in L \}$

Para idiomas regulares, o fechamento é discutido neste formulário como " Prove que os idiomas regulares estão fechados no operador de ciclo ".

Você pode tentar usar autômatos de empilhamento. Dado um autômato de empilhamento para o idioma original, construímos um para a mudança cíclica. O novo autômato opera em dois estágios, correspondendo à e à parte da palavra y x (onde x y está no idioma original). Na primeira etapa, o autómato sempre que gostaria de aparecer uma não-terminal de A , ela pode em vez empurrar um não-terminal de A ' ; a ideia é que, no final do primeiro estágio, a pilha contenha, em ordem inversa, os símbolos encontrados na pilha após a leitura de x$y$$x$$yx$$xy$$A$$A'$$x$pelo autômato original. Na segunda fase (o interruptor é não-determinístico), em vez de empurrar um não-terminal de $A$ , que estão autorizados a aparecer uma não-terminal de $A'$ . Se o autômato original puder realmente gerar a pilha após a leitura de $x$ , o novo poderá exibir exatamente a pilha inteira.

Edit: Aqui estão mais alguns detalhes. Suponha que recebamos um PDA com alfabeto $\Sigma$ , conjunto de estados $Q$ , conjunto de estados aceitantes $F$ , não terminais $\Gamma$ , estado inicial $q_0$ e um conjunto de transições permitidas. Cada transição permitida é da forma $(q,a,A,q',\alpha)$ , o que significa que, quando no estado $q$ , ao ler $a \in A$ (ou $a = \epsilon$ , nesse caso, é uma transição livre), se a parte superior da pilha é A ∈Γ (ou A = ϵ , o que significa que a pilha está vazia), o PDA pode (é um modelo não determinístico) passar para o estado q ′ , substituindo A por α ∈ Γ ∗ .$A \in \Gamma$$A = \epsilon$$q'$$A$$\alpha \in \Gamma^*$

O novo PDA tem um novo não-terminal de A ' para cada um ∈ y . Para cada dois estados q , q ′ ∈ Q e A ∈ Γ ∪ { ϵ } , existem dois estados ( q , q ′ , 1 ) , ( q , q ′ , 2 , A ) . Os estados iniciais (o estado inicial real é escolhido de forma não determinística entre eles via ϵ -transitions) são $A'$$A \in \Gamma$$q,q' \in Q$$A \in \Gamma \cup \{\epsilon\}$$(q,q',1),(q,q',2,A)$$\epsilon$q , q , 1 ) . Para cada transição ( q , a , A , q ′ , α ) existem transições correspondentes ( ( q , q ″ , 1 ) , a , A , ( q ′ , q ″ , 1 ) , α ) e ( ( 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 ) , α ) . Existem outras transições também.$((q,q'',2,B),a,A,(q',q'',2,B),\alpha)$

Para cada transição ( q , a , A , q ′ , α ) , há transições ( ( q , q ″ , 1 ) , a , B ′ , ( q ′ , q ″ , 1 ) , B ′ A ′ α ) , onde B ∈ Γ ∪ { ϵ } e ϵ ′$(q,a,A,q',\alpha)$$((q,q'',1),a,B',(q',q'',1),B'A'\alpha)$$B \in \Gamma \cup \{\epsilon\}$$\epsilon' = \epsilon$ . Para cada estado final$q \in F$ , há transições$((q,q'',1),\epsilon,A,(q_0,q'',2,\epsilon),A)$ , onde$A \in \Gamma \cup \{\epsilon\}$ .

Para cada transição ( q , a , ϵ , q ′ , α ) , há transições ( ( q , q ″ , 2 , A ) , a , B ′ , ( q ′ , q ″ , 2 , A ) , B ′ α ) , onde A ∈ Γ ∪ { ϵ } . Para cada transição$(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)$ , existem transições$((q,q'',2,B),a,A',(q',q'',2,A),\epsilon)$ , onde$B \in \Gamma \cup \{\epsilon\}$ . Para cada transição ( q , um, A , q ′ , B ) , existem "transições generalizadas" ( ( q , q ″ , 2 , C ) , a , B ′ A , ( q , q ″ , 2 , C ) , ϵ ) ; estes são implementados como uma sequência de duas transições através de um novo estado intermediário. Transições ( q , a , ϵ , q ′$(q,a,A,q',B)$$((q,q'',2,C),a,B'A,(q,q'',2,C),\epsilon)$$(q,a,\epsilon,q',\alpha)$ com$|\alpha| \geq 2$ são tratados da mesma forma. Para cada transição$(q,a,A,q',A)$ , há transições$((q,q'',2,A),a,B,(q',q'',2,A),B)$ , onde B ∈Γ ′ ∪ { ϵ } . As transições ( q , a , A , q ′ , A α ) são tratadas de maneira semelhante. Finalmente, existe um único estado final f e transições ( ( q , q , 2 , A ) , ϵ , ϵ , f , ϵ ) .$B \in \Gamma' \cup \{\epsilon\}$$(q,a,A,q',A\alpha)$$f$$((q,q,2,A),\epsilon,\epsilon,f,\epsilon)$

(Pode haver algumas transições que eu perdi e alguns dos detalhes que estou omitindo são um pouco confusos.)

Lembre-se de que estamos tentando aceitar uma palavra y x , em que x y é aceito pelo PDA original. Um estado ( q , q ′ , 1 ) significa que estamos no estágio 1, no estado q , e o PDA original está no estado q ' após a leitura de x . Um estado ( q , q ' , 2 , A ) é semelhante, onde A corresponde ao último A ' que foi disparado. No estágio 1, podemos pressionar A $yx$$xy$$(q,q',1)$$q$$q'$$x$$(q,q',2,A)$$A$$A'$$A'$em vez de popping A . Fazemos isso para cada não terminal produzido durante o processamento de x , mas apenas aparecido durante o processamento de y . Na fase 2, que estão autorizados a pop Um ' em vez de empurrar A . Se fizermos isso, teremos que lembrar que o estoque superior é realmente A ; isso se aplica somente quando não há itens "temporários" na pilha, que no PDA simulado é o mesmo que o topo da pilha sendo ϵ ou no formato B ′ .$A$$x$$y$$A'$$A$$A$$\epsilon$$B'$

Aqui está um exemplo simples. Considere um autômato para x n y n que empurre A para cada x e apareça A para cada y . O novo autômato aceita palavras de duas formas: y k x n y n - k e x k y n x n - k . Para palavras da primeira forma, o estágio 1 consiste em empurrar k vezes A ' , o estágio 2 consiste em estourar k vezes A ' , empurrando $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'$- k vezes A e popping n - k vezes A . Para palavras da segunda forma, primeiro pressionamos k vezes A , depois pop k vezes A , pressionamos n - k vezes A ' , fazemos a transição para o estágio 2 e pop n - k vezes A ' .$n-k$$A$$n-k$$A$$k$$A$$k$$A$$n-k$$A'$$n-k$$A'$

Aqui está um exemplo mais complicado, para o idioma de parênteses balanceados de vários tipos ("()", "[]", "<>"), de modo que os descendentes imediatos de cada tipo de parênteses devam pertencer a um tipo diferente. Por exemplo, "([] <>)" está OK, mas "()" está errado. Para cada "(", eu empurro A se a pilha top-of-não é A , para cada ")", nós pop A . Da mesma forma , B , C estão associados a "[]" e "<>". Aqui está como aceitamos a palavra ">) ([()] <". Nós consumimos ">)", pressionando C ′ A ′ e fazendo a transição para o estágio 2. Nós consumimos "(", popping A ' e lembrando o top-of-stack A . Nós consumimos "[()]", empurrando e estourando$A$ $A$$A$$B$$C$$C'A'$$A'$$A$B A ; ao pressionar B , sabemos que o topo da pilha "real" é A e, portanto, colchetes são permitidos (não seríamos enganados por ">) (() <"); ao pressionar A , como o topo da pilha é B (que não é ϵ ou tem a forma X ′ ), sabemos que B também é o topo da pilha "real" e, portanto, parênteses arredondados são permitidos ( mesmo que o topo da pilha de sombras seja A ). Finalmente, consumimos "<" e pop C ' .$BA$$B$$A$$A$$B$$\epsilon$$X'$$B$$A$$C'$

Considere a forma normal de Greibach . Para construir uma linguagem mudou você só precisa produções de mudança S → α A 1 ... A n a S → A 1 ... A n α e adicionar um novo não-terminal S " que se comporta como S usado para, no caso de alguma parte da produção referenciado S .$S \to \alpha A_1 \dots A_n$$S \to A_1\dots A_n \alpha$$S'$$S$$S$

Acabou sendo uma boa idéia checar o antigo clássico de Hopcroft e Ullman, Introdução à Teoria dos Autômatos (1979). O encerramento do ciclo é o Exercício 6.4c e está marcado com S **. As estrelas duplas significam que é um dos problemas mais difíceis (no livro). Felizmente, o S indica que é um dos problemas selecionados com uma solução.

A solução é a seguinte. Tome um CFG na forma normal de Chomsky. Considere qualquer árvore de derivação e basicamente vire-a de cabeça para baixo. Considere um caminho S = X 1 , X 2 , … , X n na árvore original. À esquerda, a árvore tem contribuições x 1 , x 2 , … , x n para a direita y 1 , y 2 , … , y n , significando que a sequência derivada é igual a 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 . (Na verdade, como a gramática é CNF quando o caminho continua à esquerda, a contribuição será para a direita e os correspondentes x i está vazio, etc)$x_1 x_2 \dots x_n y_n \dots y_2 y_1$$x_i$

A árvore de cabeça para baixo tem um caminho S ' , X n , ... X 2 , X 1 com contribuições y n , ... , y 2 y 1 para a esquerda e x n , ... , x 2 x 1 para a direita, portanto, o resultado é uma derivação para y n … y 2 y 1 x 1 x 2 … x n . Como requerido.$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$

Detalhes completos da construção são fornecidos no livro.

Observe como isso lembra a solução (aceita) da Yuval. Os não terminais que são enviados por push em vez de pop-up estão na ordem oposta na pilha. Muito semelhante ao contrário na árvore.