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?
formal-languages
applied-theory
computability
automata
formal-grammars
máscara de bits
fuente
fuente
Respuestas:
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.
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.
fuente
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) .
fuente
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:
Esto implica que lo siguiente nunca sucede:
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.
fuente
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 .
fuente
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).
fuente
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.
fuente
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.
fuente
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.
fuente
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.
fuente