Máquinas para lenguajes libres de contexto que no obtienen poder adicional del no determinismo

21

Cuando se consideran modelos de cómputo de máquinas, la jerarquía de Chomsky normalmente se caracteriza por (en orden), autómatas finitos, autómatas push-down, autómatas lineales y máquinas de Turing.

Para el primer y último nivel 1 (lenguajes regulares y lenguajes recursivamente enumerables), no importa el poder del modelo si consideramos máquinas deterministas o no deterministas, es decir, los DFA son equivalentes a los NFA, y los DTM son equivalentes a los NTM 2 .

Sin embargo, para PDA y LBA, la situación es diferente. Los PDA deterministas reconocen un conjunto de lenguajes estrictamente más pequeños que los PDA no deterministas. También es una pregunta abierta importante si los LBA deterministas son tan poderosos como los LBA no deterministas o no [1].

Esto provoca mi pregunta:

¿Existe un modelo de máquina que caracterice los lenguajes libres de contexto, pero para el cual el no determinismo no agrega poder adicional? (Si no, ¿hay alguna propiedad de las CFL que sugiera una razón para esto?)

Parece improbable (para mí) que sea demostrable que los lenguajes libres de contexto de alguna manera necesitan no determinismo, pero no parece haber un modelo de máquina (conocido) para el cual las máquinas deterministas sean suficientes.

La pregunta de extensión es la misma, pero para lenguajes sensibles al contexto.

Referencias

  1. S.-Y. Kuroda, "Clases de idiomas y autómatas lineales encuadernados" , Información y control, 7: 207-223, 1964.

Notas al pie

  1. Pregunta secundaria para los comentarios, ¿hay alguna razón para que los niveles (ordenados por la inclusión establecida) de la jerarquía de Chomsky sean los números 3 a 0, en lugar de 0 a 3?
  2. Para ser claros, estoy hablando de los idiomas que solo se pueden reconocer. Obviamente, las cuestiones de complejidad se ven radicalmente afectadas por dicho cambio.
formal-languages computability context-free computation-models context-sensitive Luke Mathieson
fuente
1
Entonces, ¿está preguntando por la clase de idiomas más grande (pero lo más cerca posible) de CFL para la cual la versión determinista = versión no determinista?
Ryan
@ Ryan no, estoy preguntando si hay un modelo de máquina que caracteriza a las CFL, pero para el cual las variantes no deterministas y deterministas son equivalentes en potencia, sin embargo, suponiendo que no haya una respuesta positiva (que sospecho que no existe), esa es una buena siguiente pregunta.
Luke Mathieson
3
Creo que el principal problema con la pregunta es la falta de una definición general para un "modelo computacional". Podría, por ejemplo, definir una TM determinista que esté equipada con una gramática sin contexto, que acepte una palabra si la gramática la genera. Este es un modelo determinista que es equivalente a CFL, pero es una tontería ...
Shaull
@Shaull, ese es un punto justo, pero parece difícil dar una definición para un modelo "sensible". Obviamente, su ejemplo no parece natural, pero no creo que haya una forma de definición justificable a su alrededor.
Luke Mathieson
Para vincular en la pregunta de seguimiento de Ryan , la máquina mencionada en la respuesta de Thomas Klimpel (aunque no es tan elegante como un PDA), encajaría en la idea de "natural" de una manera que una TM restringida a calcular un CFG no lo haría. Quizás la intuición es que una TM con un CFG está codificando explícitamente en la definición de un CFL, mientras que no es obvio, por ejemplo, que los CFG y PDA deberían estar relacionados, el PDA es una extensión natural de DFA y funciona para CFL .
Luke Mathieson

Respuestas:

-2

Según tengo entendido de la teoría de la computación, la única situación en la que el no determinismo no le da flexibilidad adicional (es decir, ... poder) está en el nivel recursivamente enumerable / recursivo. Esto se debe principalmente al problema de detención y sus limitaciones en las capacidades de capacidad de decisión del TM, que creo que responde a una de sus preguntas en las notas al pie, así como en una barra lateral. La Jerarquía de Chomsky es una representación lógica de subir la flexibilidad más tarde (si puedo decir), permitiendo más potencia a la máquina. ¿Ayuda esto con sus preguntas / pensamientos?

En lo que respecta a los PDA y LBA, haré que las otras personas con éxito aquí en la comunidad ayuden con eso, mi experiencia ha sido más con TM y la teoría asociada con la parte más alta (más RE) de la jerarquía (al menos como se enseña en mi estudiante)

Peter Linz teoría de la computación

https://www.amazon.com/Introduction-Formal-Languages-Automata/dp/1284077241/ref=pd_sbs_14_img_0?_encoding=UTF8&psc=1&refRID=6AA9FQJWZZNZDTQ6Z3K4

bmc
fuente
Esto no responde la pregunta. El OP ya está al tanto de lo que escribió.
Yuval Filmus