A conversão de PDA para o CFG

Question

Estou tentando entender este exemplo de conversão de PDA para o CFG mas não estou obtendo a idéia muito certo.Eu tenho a compreensão geral de um teorema que se $p,q\ \epsilon\ Q $ e $X \varepsilon\ \Gamma$ para $[pXq]$ temos de incluir a seqüência de derivações que seria pop X a partir da pilha.

Eu parcialmente entender o que está acontecendo, mas não me parecem compreender como faço para desenrolar as produções para formar cadeias de caracteres para que eu possa compreendê-lo claramente.Levar a produção (5) no exemplo de instância.Pelo que eu entendo é que estamos em estado p queremos pop e no final, devemos estar em um estado p com a pilha vazia.Como estamos lendo 0 temos zero na produção, seguido por $[pAq][qAp]$, esta é a coisa que eu não estou compreendendo porque se olharmos para o PDA não há nenhuma maneira de ir para q na leitura de 0.Eu gostaria de saber o que realmente está acontecendo.

Uma questão é respondida aqui mas eu não consigo entender é como limpar a minha confusão.

Answer 1

Você tem a intuição básica para a direita.A variável $[p,A,q]$ representa o conjunto de (cadeias de caracteres aceitos por) cálculos de estado $p$ para o estado $q$ que irá aparecer o superior, símbolo $A$ a partir da pilha.

Technicaly a relação entre gramática $G$ e pda $M$ é dada na parte superior do slide show.

Em seguida, a construção segue a recursividade.Se o pda pops $A$ mas empurra $B_1B_2B3$ a gramática vai substituir a computação em $A$ iniciar em $p$ e terminando em $q$ em três cálculos $[q_1,B_1,q_2][q_2,B_1,q_3][q_3,B_1,q]$.Aqui os estados intermediários $q_2,q_3$ são desconhecidas e estão adivinhou por gramática.Apenas $q_1$ é conhecido, como é o estado onde o pda instrução move para.

A sua observação é direito.Este padrão de construção pode apresentar trigêmeos $[p,A,q]$ que vai ser inútil.No seu exemplo não haverá cálculos de $q$ para $p$ assim, um trio de $[q,A,p]$ nunca é usado em um sucesso de derivação.Que não é problamatic.A construção só produz todas as possibilidades, e as variáveis que acabam por ser inúteis podem ser removidos depois, se alguém realmente quer.

Nota. A outra questão que o link para usa um diferente Sipser estilo autômato do modelo!Lá pilha de símbolos são colocados um por um, sem popping ao mesmo tempo.Para aumentar a confusão, o responder dada a pergunta que combina perfeitamente com a construção de sua apresentação!