Decidabilidad de las lenguas de gramáticas y autómatas

Tenga en cuenta que esta es una pregunta relacionada con el estudio en un curso de CS en una universidad, NO es tarea y se puede encontrar aquí en el examen de otoño de 20112.

Aquí están las dos preguntas que estoy viendo en un examen anterior. Parecen estar relacionados, el primero:

Dejar

$\qquad \mathrm{FINITE}_{\mathrm{CFG}} = \{ < \! G \! > \mid G \text{ is a Context Free Grammar with } |\mathcal{L}(G)|<\infty \}$

Demuestre que es un lenguaje decidible. $\mathrm{FINITE}_{\mathrm{CFG}}$

y...

Dejar

$\qquad \mathrm{FINITE}_{\mathrm{TM}} = \{ < \! M\!> \mid M \text{ is a Turing Machine with } |\mathcal{L}(M)|<\infty \}$

Demuestre que es un lenguaje indecidible. $\mathrm{FINITE}_{\mathrm{TM}}$

Estoy un poco perdido sobre cómo abordar estos problemas, pero tengo algunas ideas que creo que pueden estar en la dirección correcta. Lo primero que sé es que el lenguaje , donde$A_{\mathrm{REX}}$

$\qquad A_{\mathrm{REX}} = \{ <\! R, w \!> \mid R \text{ is a regular expression with } w \in\mathcal{L}(R)\}$

es un lenguaje decidible (la prueba está en la Teoría de la computación de Michael Sipser , p. 168). La misma fuente también demuestra que una Gramática libre de contexto se puede convertir en una expresión regular, y viceversa. Por lo tanto, también debe ser decidible, ya que puede convertirse en una expresión regular. Esto, y el hecho de que es la ONU -decidable, parece estar relacionada con este problema.$A_{\mathrm{CFG}}$$A_{\mathrm{TM}}$

Lo único que se me ocurre es pasar G a las máquinas de Turing para (después de convertir G a una expresión regular) y . Luego acepta si G lo hace y rechaza si G no. Como es indecidible, esto nunca sucederá. De alguna manera siento que estoy cometiendo un error aquí, pero no estoy seguro de qué es. ¿Podría alguien echarme una mano por favor? A T M A T $A_{\mathrm{REX}}$$A_{\mathrm{TM}}$$A_{\mathrm{TM}}$

1. Convierta G a la forma Chomsky Normal . De esta manera, la única derivación vacía sería el símbolo de inicio que no aparece en ningún otro lado y, por lo tanto, si hay alguna producción que eventualmente pueda generarse, la gramática es infinita. Si no existe tal producción, cada símbolo solo podrá generar un conjunto finito de cadenas, y luego la gramática es finita. Por lo tanto, construya un gráfico dirigido donde cada producción sea un nodo y cada símbolo dentro de una producción sea un borde dirigido a ese símbolo. Si el gráfico tiene algún ciclo, el CFG es infinito, de lo contrario no lo es. Por lo tanto, una máquina de Turing para podría construirse haciendo exactamente eso, y luego F $FINITE_{CFG}$ es decidible.$FINITE_{CFG}$

2. Suponga que es decidible. Digamos que H es una máquina de Turing que tiene alguna cadena como entrada y uso de sí mismo como una entrada a F I N I T E T H . Si F I N I T E T M devuelve verdadero (es decir, H solo acepta un lenguaje finito), entonces $FINITE_{TM}$$H$$FINITE_{TM}$$FINITE_{TM}$$H$$H$acepta la entrada, lo que lleva a una contradicción ya que el conjunto de entrada es infinito (la longitud de la entrada no tiene límites, por lo que aceptar cualquier posible cadena como entrada significa aceptar un conjunto infinito de cadenas). Si devuelve falso (es decir , el lenguaje de H es infinito), entonces H rechaza la entrada, lo que significa que el lenguaje de H es finito porque no acepta ninguna entrada (es decir, su idioma está vacío), lo que lleva a una contradicción también. De esta manera, la suposición de que H existe conduce a la contradicción, y esta suposición se basa en la suposición de que F I N I $FINITE_{TM}$$H$$H$$H$$H$ es decidible. Entonces, por contradicción, tenemos que F I N I T E T M no es decidible.$FINITE_{TM}$$FINITE_{TM}$

La misma fuente también demuestra que una Gramática libre de contexto se puede convertir en una expresión regular, y viceversa.

Realmente dudo que Sipser diga eso, probablemente leíste mal o lo entendiste mal. Esto significaría que las gramáticas libres de contexto generan exactamente los mismos idiomas que las gramáticas lineales derechas. Esto es falso Las gramáticas lineales derechas que se generan son un subconjunto adecuado de las gramáticas sin contexto dp. Dicho esto, la forma en que trataste de usar idiomas regulares para responder las preguntas simplemente te lleva a ninguna parte.

Como puede ver arriba en mis pruebas, las dos preguntas son de hecho dos preguntas muy distintas y no relacionadas. Simplemente sucede que fueron redactados de manera similar.

Otra forma de decidir es a través del lema de bombeo.$FINITE_{CFG}$

El lema de bombeo dice que cada CFL tiene un número N (que puede calcularse a partir de la gramática, o al menos un límite superior puede calcularse fácilmente), de modo que cualquier x ∈ L que sea más largo que N puede "bombearse ".$L$$N$$x\in L$$N$

Esto significa que si es finito, todas las palabras que L son más cortos que N .$L$$L$$N$

$N$$2N$$L$$L$