Encontrar un autómata de empuje para el lenguaje $|w|_a = |w|_b$

Question

Soy nuevo en esto de los autómatas push down y no sé cómo encontrar uno para el siguiente idioma:

$$L=(w \in A^:|w|_a=|w|_b) \enspace.$$

También tengo que demostrar que mi construcción es correcta. ¿Puede alguien mostrarme cómo se hace o darme un ejemplo?

Answer 1

Supongamos que el g.e.v. $A = \{a,b\}$ . Informalmente, podemos construir un PDA que tenga dos estados de "conteo", en su primer estado empuja un símbolo en su pila por cada $a$ sus lecturas, y lo hace para cada $b$ en el otro estado funciona al revés, es decir, empuja un símbolo por cada $b$ y aparece uno para cada $a$ . Y cada vez que su pila está vacía, el estado que toma después de leer el siguiente símbolo es el primer estado si lee un $a$ siguiente, o el segundo en caso contrario.

Para la construcción formal, según la definición citada de la wikipedia, no podemos comprobar si la pila está vacía en el curso del cálculo. Por lo tanto, utilizamos un símbolo especial $\gamma_0$ que siempre está en la parte inferior de la pila. Entonces, en lugar de aceptar por pila vacía, como está escrito en la descripción informal anterior, la PDA acepta si se lee el símbolo de inicio de pila, no estamos en el estado de inicio y hemos procesado todos los símbolos de la entrada.

Dejemos que $\mathcal M = (Q, A, \Gamma, \delta, q_a, \gamma_0, F)$ ser un autómata de empuje , donde $\Gamma = \{\gamma_0, \gamma\}$ y $Q = \{q_a, q_b\}, F = \{q_a, q_b\}$ con transiciones \begin{align*} & (q_a, a, \gamma_0, q_a, \gamma\gamma_0) \\ & (q_a, b, \gamma_0, q_b, \gamma\gamma_0) \\ & (q_a, a, \gamma, q_a, \gamma\gamma) \\ & (q_a, b, \gamma, q_a, \varepsilon) \\ & (q_b, a, \gamma, q_b, \varepsilon) \\ & (q_b, b, \gamma, q_b, \gamma\gamma) \\ & (q_b, b, \gamma_0, q_b, \gamma\gamma_0) \\ & (q_b, a, \gamma_0, q_a, \gamma\gamma_0). \end{align*} Entonces \begin{align*} L(\mathcal M) & = \{ w \in A^{\ast} \mid (q_a, w, \gamma_0) \vdash_{\mathcal M}^{\ast} (q, \varepsilon, u), q \in F, u \in \Gamma^{\ast} \} \\ & = \{ w \in A^{\ast} \mid (q_a, w, \gamma_0) \vdash_{\mathcal M}^{\ast} (q, \varepsilon, \gamma_0), q \in F \} \\ & = \{ w \in A^{\ast} \mid |w|_a = |w|_b \}. \end{align*} Tenga en cuenta que no importa si usamos $q_a$ o $q_b$ como estado inicial. Para la prueba de que esta construcción es correcta, nótese que si la PDA acepta una palabra los únicos puntos en los que puede cambiar su estado son cuando $\gamma_0$ es el único símbolo de la pila, y por construcción esto ocurre cuando hasta este punto, el número de $a$ equivale al número de $b$ mediante las correspondientes operaciones push/pop, por lo que al final el número de $a$ y $b'$ deben ser iguales. Para la otra dirección supongamos $w$ tiene un número igual $a$ y $b$ y a continuación escriba $w = w_1 w_2 \cdots w_k$ donde cada $w_i$ tiene una longitud no vacía $|w_i| > 0$ y es tal que cada prefijo del mismo tiene un número desigual de $a$ y $b'$ es decir $w_i = a^n b^n$ o $w_i = b^n a^n$ . Entonces es fácil ver que la PDA funciona a través de esta palabra donde entre el $w_i$ sólo tiene $\gamma_0$ en su pila, y mientras se procesa algún $w_i$ se encuentra en el estado $q_a$ o $q_b$ y procesarlas correctamente según su forma. $\square$