¿Cómo demuestro que si un PDA acepta alguna cadena

¿Cómo demuestro que el problema de decidir si un PDA acepta alguna cadena de la forma es indecidible?$\{ w!w \mid w \in \{ 0, 1 \}^*\}$

He tratado de reducir este problema a otro indecidible, como si dos gramáticas libres de contexto aceptan el mismo lenguaje. Sin embargo, no estoy seguro de cómo usarlo como una subrutina.

Aquí está mi enfoque: mostraré que si puede decidir su problema, entonces puede decidir el problema de correspondencia de Post (PCP), que se sabe que no es decidible.

Recuerde, PCP es un problema de decisión que pregunta si en un conjunto de $2$-tuplas $P=\{(x_1,y_1),\ldots,(x_n,y_n)\}$ puede construir una secuencia (incluida la repetición) de manera que la concatenada $x_i$sy los concatenados $y_i$s de esta secuencia forman la misma palabra. Tenga en cuenta que el alfabeto debe tener al menos 2 caracteres.

Entonces deja $P$ser una instancia del PCP. Considere la siguiente gramática libre de contexto, donde hemos introducido un nuevo símbolo de terminal$t_i$ Para el $i$-th elemento en $P$. La gramática tiene las siguientes reglas:

Por supuesto, dada cualquier gramática, podemos encontrar un PDA correspondiente que acepte el mismo lenguaje que la gramática. Por lo tanto, construya el PDA correspondiente y luego use el algoritmo hipotético de su problema para determinar si este PDA acepta alguna palabra del formulario$u!v$ (es decir, si se puede derivar alguna palabra de la forma $u!v$de esta gramática). Mostraré cómo usar esta información para resolver la instancia de PCP$P$.

Supongamos ahora que $u!v$Es una palabra en esta gramática. La palabra$u$ tiene dos partes, el sufijo, que consiste en el $t_i$terminales, y el resto llamado prefijo. Lo mismo es cierto de$v$. Tenemos$u=v$si y solo si sus prefijos y sufijos coinciden. Los sufijos coinciden solo si hemos usado la misma secuencia de tuplas de$P$ para construir las palabras $u$ y $v$. Los prefijos de$u$ y $v$ coincidir si la concatenación de la $x_i$s y $y_i$s (basado en la secuencia de tuplas invertida dada por el $t_i$s) es lo mismo. Por lo tanto$u=v$ si y solo si hay una solución para la instancia PCP $P$.

Del mismo modo, si hay una solución para la instancia de PCP $P$, a partir de la solución, es fácil construir una palabra de la forma $u!v$ eso es derivable de esta gramática.

Se deduce que la instancia de PCP $P$ tiene una solución si y solo si esta gramática contiene una palabra de la forma $u!v$. Si hubiera un algoritmo para decidir su problema, podríamos usarlo para resolver PCP. Pero, por supuesto, se sabe que PCP es indecidible, por lo que su problema también es indecidible.

El enfoque podría ser el siguiente. Intente crear un lenguaje libre de contexto (= PDA) que codifique los pasos de cálculo de una TM, de modo que el cálculo completo sea exitoso si hay una palabra de la forma que usted describe.

Primero debe codificar configuraciones separadas: contenido de la cinta + estado + cabezal de posición (lo habrá visto para la equivalencia gramatical). Un lenguaje sin contexto puede codificar un solo paso$C\vdash C'$ de un cómputo siempre que use una imagen espejo $C\#m(C')$, dónde $m(C)$denota la imagen especular (inversión) de $$ C $. (Soy descuidado aquí: puede que tenga que distinguir la configuración y su descripción).

Ahora considere el lenguaje de pasos separados, concatenados con el lenguaje de configuraciones duplicadas: $C_0\#C_1\#m(C_2)\#C_3\#m(C_4)\# \dots C_{2n-1}\#m(C_{2n})\#C_f!$ $C'_1\#m(C'_1)\#C'_2\#m(C'_2)\#\dots C'_{n+1}\#m(C'_{n+1})$ con por cada $k$, $C_{2k-1} \vdash (C_{2k})$. Esto es libre de contexto, además de código$C_0$ como inicial y $C_f$ como configuraciones finales.

Ahora la primera parte garantiza que tengamos pasos consecutivos, la segunda parte que las configuraciones sucesivas son iguales. Si ambas partes coinciden, tenemos un cálculo. Lo cual no podemos decidir.

Esa es la idea. Puedo tener algunos índices incorrectos, y toda la secuencia tiene que estar codificada en binario, pero eso se puede resolver.