Estoy atrapado resolviendo el siguiente ejercicio:
Argumenta que si tiene contexto y es regular, entonces (es decir, el cociente correcto ) no tiene contexto.R L / R = { w ∣ ∃ x ∈ R
Sé que no debería existir un PDA que acepte y un AFD que acepte . Ahora estoy tratando de combinar estos autómatas con un PDA que acepte el cociente correcto. Si puedo construir eso, probé que tiene contexto. Pero estoy atrapado construyendo este PDA.R L / R
Esto es lo lejos que he llegado:
En el PDA combinado, los estados son un producto cartesiano de los estados de los autómatas separados. Y los bordes son los bordes del DFA pero solo aquellos para los que en el futuro se puede alcanzar un estado final del PDA original de L. Pero no sé cómo escribirlo formalmente.
Respuestas:
Aquí hay una pista.
Necesita que su máquina acepte inicialmente parte de una palabra de , consumiendo la cinta a medida que avanza. Luego, sin consumir nada, necesita encontrar alguna palabra de que empuje la máquina a un estado final. La palabra elegida de juega el papel de la palabra de entrada para la segunda mitad del cálculo.R RL R R
Claramente, el no determinismo tendrá un papel, al igual que el producto entre las dos máquinas. El truco para formalizar esto es ajustar el producto para lidiar con el hecho de que la entrada proviene de no de la entrada.R
fuente
No estoy seguro de a qué te refieres con el producto cartesiano; Esto simula ambos autómatas en paralelo, lo que le dará la intersección. ¡Pero desea que identifique todas las palabras en que tienen un sufijo de R ! En un nivel intuitivo, eso es.L R
Supongamos que nuestra entrada es . Obviamente, no podemos verificar todas las continuaciones posibles (para ser miembro de R ), sino solo un número finito de ellas. El comentario de Artem es más útil aquí; que adivinar lo que el sufijo x va a ser, y ejecutar tanto autómatas en él.w ∈ Σ∗ R X
También puedes usar gramáticas formales. ¿Ves cómo puedes derivar en dos gramáticas en paralelo? En general, no está claro cómo adaptar para que pueda manejar los sufijos; utilizando la forma normal de Chomsky ayuda.GL
fuente
Recomiendo usar la respuesta de Raphael, que es mucho más fácil de entender, pero aquí hay una alternativa, usando propiedades de cierre en lugar de autómatas:
Más formalmente:
fuente