¿Cuál es el significado de los lenguajes sensibles al contexto (Tipo 1)?

34

Al ver que en la Jerarquía de Chomsky, los lenguajes Tipo 3 pueden ser reconocidos por una máquina de estado sin memoria externa (es decir, un autómata finito), el Tipo 2 por una máquina de estado con una sola pila (es decir, un autómata pushdown) y el Tipo 0 una máquina de estados con dos pilas (o, equivalentemente, una cinta, como es el caso de las máquinas de Turing), ¿cómo encajan los idiomas de Tipo 1 en esta imagen? ¿Y qué ventajas trae para determinar que un idioma no es solo Tipo 0 sino Tipo 1?

máscara de bits
fuente
2
Como está preguntando aquí y no en cstheory.SE (como lo sugiere @Sunil), le sugiero que también agregue una breve descripción / definición del Tipo 1, que podría no ser un término familiar para todos.
Janoma
55
@Sunil No, no lo haría. Esta no es una pregunta de nivel de investigación (e incluso si lo fuera, todavía estaría en el tema aquí porque no excluimos las preguntas de nivel de investigación, al menos eso es lo que recuerdo haber sido el resultado de la discusión en el área51).
sepp2k
3
@Janoma: ¿Por qué debería ayudar incluir información que pueda consultarse fácilmente (¿no sería eso un ruido?)
máscara de bits
44
@ Janan Creo que la pauta general debería ser explicar los conceptos que alguien que podría responder la pregunta podría no saber (si la pauta explicara todo lo que algunos usuarios del sitio podrían no saber, estaríamos explicando todo todo el tiempo y ciertamente no es el estándar en otros sitios de SE). Y no creo que alguien que no conozca la jerarquía de Chomsky pueda responder la pregunta. Por supuesto, no está de más explicarlo tanto como sea posible (siempre que no haga que la pregunta sea tediosamente larga). Simplemente no creo que sea necesario en este caso.
sepp2k
44
Cada estudiante de informática conoce (o debería saber) la jerarquía de Chomsky. Todos los demás pueden buscarlo en 20 años. Un enlace a quizás Wikipedia debería ser suficiente aquí.
Raphael

Respuestas:

19

PSPACE

Comparando esto con los idiomas de tipo 0, esto significa que al menos puede decir algo sobre cuánto tiempo lleva reconocer el idioma. Un lenguaje de tipo 0 puede que ni siquiera sea decidible: el lenguaje de todas las máquinas de Turing que se detienen es un lenguaje de tipo 0, pero como reconocer este idioma es exactamente el problema, no es decidible.

PSPACE

La razón de su existencia es que forman una extensión muy natural de las gramáticas libres de contexto (permite que el contexto determine qué producciones son válidas). Esto probablemente habrá inspirado a Chomsky a definirlos y nombrarlos como idiomas tipo 1. Recuerde que esta definición se hizo antes de que las computadoras se volvieran tan rápidas como lo son hoy: es más interesante para los teóricos del lenguaje formal que para los programadores.

Las gramáticas sin restricciones se vuelven aún más extrañas: ya no existe la noción de 'expandir' un no terminal y reemplazarlo con una producción, posiblemente dependiendo del contexto. También puedes modificar libremente el contexto. Esto hace que las gramáticas sin restricciones sean aún menos intuitivas para trabajar: los programas son equivalentes y mucho más intuitivos.

Alex ten Brink
fuente
¡Pero los lenguajes sensibles al contexto son útiles! Ver, por ejemplo, esta discusión .
Raphael
La sensibilidad al contexto es útil, pero las gramáticas sensibles al contexto como una forma de describir idiomas no son muy útiles en mi opinión. Es mucho mejor usar otros medios para describir características sensibles al contexto.
Alex ten Brink
Pero usted habla de idiomas en la mayoría de las partes de su respuesta. En cuanto a las gramáticas, mmm. Existen modelos gramaticales entre CFG y CSG que tienen aplicaciones de modelado natural, por ejemplo, acoplado / multi-CFG.
Raphael
1
Tienes razón, he sido descuidado con la distinción entre idiomas y gramáticas que veo. He actualizado mi respuesta.
Alex ten Brink
10

L

AL(A)

En resumen, para clases más pequeñas necesita menos potencia de cálculo para resolver el problema de decidir si una palabra pertenece al idioma.

Según Wikipedia , Chomsky definió gramáticas sensibles al contexto (es decir, Tipo 1) para describir la sintaxis de los lenguajes naturales. Esto es un poco diferente que con otras clases de idiomas, que se introdujeron para describir familias de cadenas que se usaron en matemáticas (por ejemplo, la sintaxis de fórmulas aritméticas) en lugar de los lenguajes naturales (por ejemplo, la sintaxis de una oración gramaticalmente correcta en inglés) .

Janoma
fuente
2
"En resumen, para clases más pequeñas se necesita menos potencia computacional para resolver el problema de decidir si una palabra pertenece al idioma". exactamente, pero ¿cómo se aplica esto al Tipo 1 frente al Tipo 0? Esa es exactamente la pregunta!
bitmask
ccn
8

En lenguajes libres de contexto, en cualquier punto del análisis de entrada, el autómata se encuentra en un estado definido por su pila. Cada producción tiene el mismo comportamiento al consumir la entrada, independientemente de dónde se use.

Esto lleva a la propiedad interesante de que cada producción genera un sublenguaje del generado por los que están más profundos en la pila y, por lo tanto, para cada par A y B de producciones generadas y consumidas en cualquier entrada particular, tenemos tres casos posibles:

  • a: La entrada consumida por A está completamente contenida en la entrada consumida por B; o
  • b: La entrada consumida por A contiene completamente la entrada consumida por B; o
  • c: La entrada consumida por A es completamente disjunta de la entrada consumida por B.

Esto implica que lo siguiente nunca sucede:

  • d: La entrada consumida por A se superpone parcialmente a la entrada consumida por B.

En contraste con eso, en los lenguajes sensibles al contexto, el comportamiento de cada producción depende de dónde se usa, por lo que la entrada consumida en una producción no es un sub-idioma de los más profundos en la pila (de hecho, procesándolo con un la pila no funcionaría). Y tenemos esa posibilidad d puede suceder.

En el mundo real, un caso en el que un lenguaje sensible al contexto tendría sentido es algo así como denotar <b> texto en negrita </b>, <i> texto en cursiva </i> y <u> texto subrayado </u> con estas etiquetas html y deja que se superpongan, como "Este es un <u> texto con <i> mezclado </u> etiquetas superpuestas </i>". Observe que para analizar eso y encontrar si todas las etiquetas iniciales coinciden con las etiquetas finales, un PDA no funcionará porque no está libre de contexto, pero un LBA lo hará fácilmente.

Victor Stafusa
fuente
7

Propiedades de cierre

De todas las clases de idiomas de la jerarquía de Chomsky, solo los lenguajes regulares y sensibles al contexto están cerrados bajo complementación . Por lo tanto, esta es una especie de característica única de los lenguajes sensibles al contexto.

A diferencia de los lenguajes libres de contexto, los CS también se cierran bajo intersección y producto aleatorio .

Sebastian
fuente
6

Cualquier lenguaje que sea de tipo 1 puede ser reconocido por una máquina de Turing que solo usa espacio lineal (los llamados autómatas lineales delimitados).

Suresh
fuente
2
Sí, esa es la definición. Pero, ¿cómo me ayuda esta restricción?
bitmask
3
me ayuda porque limita el poder de los algoritmos que reconocen CSG a E en lugar de EXP. No sé cómo te ayuda :)
Suresh
5

Los lenguajes de tipo 1 pueden decidirse por autómatas lineales acotados , que son máquinas de Turing no deterministas que solo pueden usar una parte de la cinta cuyo tamaño es lineal al tamaño de entrada.

sepp2k
fuente
4

La jerarquía de Chomsky clasifica las gramáticas más que los idiomas. Sin embargo, no fue diseñado para tener algo que ver con la cantidad de cintas que un autómata debería reconocer, como sugirió para los tipos 2 y 3, incluso si hay un tipo de máquina de Turing que lo haga para las gramáticas Tipo-1.

También debe tener en cuenta que una máquina de Turing no reconoce todos los idiomas de las gramáticas de tipo 0, pero solo puede enumerarlos una máquina de este tipo: tipo 0 significa enumerable recursivamente, y las máquinas de Turing solo reconocen idiomas recursivos.

jmad
fuente
4

El lenguaje de programación moderno usa características sensibles al contexto todo el tiempo; caen en un subconjunto que se puede decidir eficientemente.

Ejemplos son el análisis de nombres y tipos y la inferencia de tipos.

Rafael
fuente
3

Muchos otros han mencionado que los lenguajes Tipo 1 son aquellos que pueden ser reconocidos por autómatas lineales. El problema de detención es decidible para los autómatas lineales delimitados, lo que a su vez significa que muchas otras propiedades que son computacionalmente indecidibles para los idiomas reconocidos por Turning Machines son decidibles para los lenguajes Tipo-1.

Es cierto que la prueba de que el problema de detención es decidible para los autómatas lineales confiados se basa en el hecho de que con una cantidad finita de cinta solo pueden ingresar un número finito de estados, por lo que si no se detienen dentro de tantos pasos, sabes que son bucle y nunca se detendrá. Esta prueba se aplica técnicamente a todas las computadoras reales (que también tienen memoria finita), pero eso no tiene ningún beneficio práctico para resolver el problema de detención de los programas que se ejecutan en ellas.

Ben
fuente