¿Todos los lenguajes sensibles al contexto son decidibles?

12

Estaba revisando la definición de Wikipedia de lenguaje sensible al contexto y encontré esto:

Cada categoría de idiomas es un subconjunto apropiado de la categoría directamente encima de ella. Cualquier autómata y cualquier gramática en cada categoría tiene un autómata o gramática equivalente en la categoría directamente encima de ella.

Pude ver que el autómata con límite lineal está directamente debajo del decisor en el pedido del artículo. Si este es el caso, eso significa que todos los cálculos en un LBA se detendrán en algún momento (ya que cada LBA sería decisivo). Pero siento que puede haber algunos cálculos que pueden ejecutarse en un LBA al mismo tiempo para nunca detenerse. Por ejemplo, podemos escribir un cálculo en LBA que

  1. lea el primer símbolo en la cinta y muévase a la derecha;
  2. lea el siguiente símbolo y retroceda a la izquierda.

Este cálculo (inútil) (que obviamente es un cálculo LB) se ejecutaría oscilando indefinidamente a izquierda y derecha y nunca se detendría y, por lo tanto, no puede ser decisivo. ¿Dónde estoy pensando mal?

formal-grammars turing-machines undecidability context-sensitive bongubj
fuente
1
Decidir un CSL es independiente de si hay un LBA sin terminación: solo tiene que existir un LBA para él.
Raphael

Respuestas:

9

Primero, todos los lenguajes sensibles al contexto son decidibles, ya que pueden ser aceptados por un LBA (como usted dijo), y una máquina Turing es más poderosa que un LBA.

MM′MM′

A.Schulz
fuente
Si alguien aún no entendió esta respuesta, le sugiero que consulte la Diapositiva 3-4 de esta presentación para obtener una explicación adicional.
bongubj
0

Le sugiero que eche un vistazo a este libro: Introducción a los idiomas y la teoría de la computación por John E Martin

página 283: Todavía hay preguntas abiertas sobre los lenguajes sensibles al contexto, como por ejemplo si un CSL determinista puede aceptar o no todas las CSL.

Amir Nikabadi
fuente
¿Cómo responde esto a la pregunta? Los lenguajes sensibles al contexto son todos decidibles, independientemente de si necesita un espacio lineal determinista o no determinista.
Yuval Filmus