Empuje hacia abajo el problema de autómatas

Question

De manera informal describir los no deterministas PDA que genera:

$$\{x\#y\ \mid x,y\in\{a,b\}^{*}\text{and}\space x\ne y\}$$

Mi plan inicial era utilizar no determinismo ir a través de cada personaje antes y después de la # y tratar de coincidir con ellos, y si no coinciden, a continuación, aceptar. Así que me gustaría comprobar el primer char contra el primer carácter después de #, etc. Sin embargo yo no puedo conseguir que esta idea ya que me parece que no puede récord en la posición de carácter después de la # así como el carácter necesito partido contra antes de la # con la sola pila.

Gracias por la ayuda.

Answer 1

Considere los siguientes idiomas: $$\newcommand{\A}{\mathtt{un}} \newcommand{\B}{\mathtt{b}} \newcommand{\P}{\mathtt{\#}}\begin{gather} L_\text{long} = \{ x \P y : x , y \in \{ \A , \B \}^* , | x | > | y | \};\\ L_\text{short} = \{ x \P y : x , y \in \{ \A , \B \}^* , | x | < | y | \};\\ L_\text{diff} = \{ x \P y : x , y \in \{ \A , \B \}^* , | x | = | y |, ( \exists k ) ( x_k \neq y_k ) \}. \end{se reúnen}$$ Tenga en cuenta que su lengua $L$ es claramente la unión de estos tres idiomas, por lo que no deterministas PDA para $L$ primero nondeterministically elegir cuál de estos tres idiomas de la cadena pertenece a y, a continuación, compruebe que la cadena pertenece al lenguaje. (No determinista) Pda para $L_\text{long}$ e $L_\text{short}$ son relativamente fáciles de construir, la verdadera dificultad es con $L_\text{diff}$.

No estoy diciendo que los $L_\text{diff}$ es independiente del contexto (yo realmente no creo que lo es), pero hay un contexto de un lenguaje libre que incluye a $L_\text{diff}$ como un sub-lenguaje, y es en sí mismo un sub-lenguaje de $L$: vamos a $L^\prime_{\text{diff}}$ consta de todas las cadenas $w \in \{ \A , \B , \P \}^*$ tal que

• $\P$ ocurre exactamente una vez en $w$; y
• si $w^\prime$ es la cadena que se obtiene por extracción de la instancia única de $\P$ en $w$,, a continuación,$w^\prime \in \{ xy \in \{ \A , \B \}^* : |x| = |y| , x \neq y \}$.

Debe quedar claro que $L_\text{diff}$ es un sub-lenguaje de $L_\text{diff}^\prime$, y cada cadena en $L_\text{diff}^\prime$ pertenece a $L$.

Supongamos que $x = x_1 \cdots x_n$ e $y = y_1 \cdots y_n$ son tales que $x \neq y$. Esto significa que hay un $k \leq n$ tal que $x_k \neq y_k$: por el momento, supongamos $x_k = \A$ e $y_k = \B$. Entonces podemos reescribir nuestra cadena como $$x y = x_1 \cdots x_{k-1} \;\A\; x_{k+1} \cdots x_n \; y_1 \cdots y_{k-1} \;\B\; y_{k+1} \cdots y_n$$ Note that the substring $x_{k+1} \cdots x_n \; y_1 \cdots y_{k-1}$ has length $(n-k) + (k - 1 ) = n - 1$ and so let us write it as $$z_1 \cdots z_{k-1} z_k \cdots z_{n-1}$$ Entonces $$\begin{align} xy &= x_1 \cdots x_{k-1} \;\A\; x_{k+1} \cdots x_n \; y_1 \cdots y_{k-1} \;\B\; y_{k+1} \cdots y_n \\ &= \overbrace{x_1 \cdots x_{k-1}}^{\text{length } k-1}\; \A\;\overbrace{z_1 \cdots z_{k-1}}^{\text{length } k-1} \; \overbrace{z_k \cdots z_{n-1}}^{\text{length }n-k} \;\B\; \overbrace{y_{k+1} \cdots y_n}^{\text{length }n-k} \end{align}$$ Así, la cadena $xy$ puede ser visto como la concatenación de dos cadenas de longitud impar $u , w$ que tienen diferentes medio de símbolos. Una vez que esto se observa, es relativamente fácil construir un no deterministas PDA para este idioma. (Primer no-determinista decidir si la primera subcadena tiene un $\A$ como su medio de símbolos y el segundo, un $\B$, o viceversa, al leer la primera cadena de pop en un símbolo en la pila hasta que no determinista adivinar el centro el símbolo de la primera subcadena, y a continuación, el pop de los símbolos off; una vez que el juego es nuevo vacío pop símbolos y no de manera determinista adivinar, donde la media símbolo de la segunda cadena.)

Para obtener un no deterministas PDA para $L_\text{diff}^\prime$ también asegurarse de que usted encuentre uno (y sólo uno) $\P$ en la cadena antes de aceptar (pero de la lectura de un $\P$ no afecta a la pila de alguna manera).

Answer 2

Esto es en realidad más fácil de lo que Arthur Fischer es lo que es. Podemos hacer más uso de ese $\#$ marcado la mitad de la cuerda. Mi respuesta es en realidad mucho a lo largo de las líneas de lo que usted dijo que se trató, creo. Supongo que podría haber sido el olvido de que está permitido más de un estado, lo que hace que sea un poco más fácil para construir el autómata.

Llame a su idioma $L$ y deje $X = \{a,b\}$. Deje $L_1 = \{u\# w \mid u,w\in X^*, |u|\neq |w|\}$ y deje $L_2$ ser el lenguaje de todas las cadenas $u\# w$ con $u,w\in X^*$ e $u_i\neq w_i$ para algunos $i\leq \min\{|u|, |w|\}$. A continuación, su idioma es el (no disjuntos), unión de $L_1$ e $L_2$. (Estoy usando $|u|$ para la longitud de $u$.)

Reconociendo $L_1$ con un pushdown autómata es muy fácil. Para reconocer $L_2$, tienen además el inicio del estado de $q_0$ cinco estados $p_a$, $p_b$, $q_a$, $q_b$ y $q$, siendo la última la de aceptar sólo estado. El uso de una sola pila el símbolo de $X$. En $q_0$, ponemos una $X$ en la pila cada vez que leemos un símbolo. Si leemos $\#$ en $q_0$, el autómata debe fallar, ya que $q_0$ es para la lectura de la palabra $u$ en $u\# w$. En cualquier momento, podemos no determinista supongo que hemos alcanzado el punto en que $u_i\neq w_i$. En este caso, pasar a estado $p_x$ donde $x$ es el símbolo que acaba de leer. En este punto tenemos $i-1$ $X$'s en la pila.

En el estado $p_x$, podemos leer sin modificar la pila o el cambio de estado hasta que se lee un $\#$, momento en el que nos movemos en el estado $q_x$. Aquí, nos aparecerá una $X$ de descuento en la pila para cada símbolo de leer. Cuando la pila está vacía, el autómata falla a menos que el siguiente símbolo de leer no es $x$, caso en el cual se mueve a $q$ y acepta.

(Nota, de la manera que he descrito esto muestra que $X$ igual podría ser cualquier alfabeto finito. También, es posible utilizar menos los estados, si lo prefiere.)