autómata de empuje, dos idiomas son posibles (condición OR)

Aug 16 2020

En la tarea conseguimos construir un autómata pushdown para 2 idiomas, pero en mi opinión estos son dos ejercicios para los que el autómata es el mismo para ambos.

Según tengo entendido, podemos construir un autómata de empuje no determinista, y cada vez que leemos el carácter a, podemos insertar una sola A o dos A, a "discreción" del autómata.

A continuación, se construye un estado para el carácter b, que cada vez que lea A lo sacará de la pila. De esta forma, el autómata sabe manejar ambos lenguajes donde la cantidad de a es igual a la cantidad de b, y también lenguajes donde como a es el doble de b.

Estoy en lo cierto? ¿O me estoy perdiendo algo?

Si no es así, me encantaría saber cómo lidiar con la condición "o" en el primer ejercicio.

Gracias.

Respuestas

2 BrianM.Scott Aug 16 2020 at 09:32

Ya que $L_2\ne L_3$, claramente no pueden ser aceptados por el mismo autómata de empuje. Parece que tienes en mente un autómata que reconoce$L_3$. Probablemente la forma más fácil de diseñar uno para reconocer$L_2$, es diseñar dos autómatas pushdown deterministas, uno para $\{a^nb^n:n\in\Bbb N\}$ y uno para $\{a^{2n}b^n:n\in\Bbb N\}$. Luego combínelos en un solo autómata de empuje que tenga transiciones$\langle q_0,\varepsilon,Z,q_1,Z\rangle$ y $\langle q_0,\varepsilon,Z,q_2,Z\rangle$, dónde $q_0$ es el estado inicial de la PDA combinada, $Z$ es el símbolo de pila inicial, y $q_1$ y $q_2$son los estados iniciales de los dos autómatas pushdown subsidiarios. En otras palabras, lo primero que hace el PDA combinado es 'elegir' si buscar una palabra del tipo$a^nb^n$ o una palabra del tipo $a^{2n}b^n$, y luego persigue esa elección de manera determinista.