Convertir PDA a CFG

Question

Estoy tratando de entender este ejemplo de convertir PDA a CFG, pero no estoy obteniendo la idea de lo correcto. Tengo la comprensión general del teorema de que si $ p, q \ \ epsilon \ q $ y $ x \ varepsilon \ \ Gamma $ para $ [pxq] $ Tenemos la secuencia de derivaciones que se enviarían x de la pila.

Entiendo parcialmente lo que está sucediendo, pero parece que no puedo entender cómo desenrollar las producciones para formar cadenas para que pueda entenderlo claramente. Tome la producción (5) en el ejemplo, por ejemplo. Por lo que entiendo, estamos en estado P queremos hacer un abrir un y al final, deberíamos estar en estado P con pila vacía. Como estamos leyendo 0 tenemos cero en la producción seguido de $ [PAQ] [QAP] $ , esta es la cosa que soy No entendiendo porque si nos fijamos en la PDA, no hay forma de ir a Q en la lectura 0. Me gustaría saber lo que realmente está pasando.

Se responde a una pregunta relacionada aquí Pero no puedo entenderlo cómo limpiar mi confusión.

Answer 1

Tienes el derecho de intuición básica. La variable $ [P, A, Q] $ representa el conjunto de (cuerdas aceptadas por) cálculos de estado $ p $ para establecer $ Q $ que aparecerá el símbolo más alto $ a $ de la pila.

técnico La relación entre gramática $ g $ y PDA $ m $ se da en la parte superior de la diapositiva que muestres.

Entonces la construcción sigue la recursión. Si la PDA pops $ a $ pero empuja $ b_1b_2b3 $ La gramática reemplazará el cálculo en $ A $ comenzando en $ p $ y terminando en $ q $ < / SPAN> en tres cálculos separados $ [q_1, b_1, q_2] [q_2, b_1, q_3] [q_3, b_1, q] $ . Aquí los estados intermedios $ q_2, q_3 $ son desconocidos y son adivinados por la gramática. Solo $ q_1 $ se conoce, ya que es el estado en el que se mueve la instrucción PDA.

Tu observación es correcta. Esta construcción estándar podría introducir triplets $ [P, A, Q] $ que será inútil. En su ejemplo, no habrá cálculo de $ q $ a $ P $ por lo que un triplete $ [Q, A, P] $ nunca se usa en una derivación exitosa. Eso no es probable. La construcción solo produce todas las posibilidades, y las variables que resultan ser inútiles se pueden quitar después, si lo realmente quiere.

nota. la otra pregunta que vincula para usar un modelo de autómata de estilo Sipser diferente! Hay símbolos de pila se empujan uno por uno sin aparecer al mismo tiempo. Para agregar a la confusión la respuesta ¡Dada en esa pregunta, coincide perfectamente con la construcción de su diapositiva!