Lenguaje determinista libre de contexto

En la teoría del lenguaje formal , los lenguajes libres de contexto deterministas ( LCPD ) constituyen un subconjunto propio de los lenguajes libres de contexto . Son lenguajes libres de contexto que pueden ser aceptados por un autómata de pila determinista . Los LCPD son siempre no ambiguos, lo que significa que admiten una gramática no ambigua . Existen lenguajes libres de contexto no deterministas no ambiguos, por lo que los LCPD forman un subconjunto propio de los lenguajes libres de contexto no ambiguos.

Los DCFL son de gran interés práctico, ya que pueden analizarse en tiempo lineal , y diversas formas restringidas de DCFG admiten analizadores prácticos sencillos. Por lo tanto, se utilizan ampliamente en la informática.

La noción de DCFL está estrechamente relacionada con el autómata de pila determinista (DPDA). Es donde se reduce la capacidad de lenguaje de los autómatas de pila si los hacemos deterministas; los autómatas de pila se vuelven incapaces de elegir entre diferentes alternativas de transición de estado y, en consecuencia, no pueden reconocer todos los lenguajes libres de contexto. ^{[ 1 ]} Las gramáticas no ambiguas no siempre generan un DCFL. Por ejemplo, el lenguaje de palíndromos de longitud par en el alfabeto de 0 y 1 tiene la gramática libre de contexto no ambigua S → 0S0 | 1S1 | ε. Una cadena arbitraria de este lenguaje no puede ser analizada sin leer primero todas sus letras, lo que significa que un autómata de pila tiene que intentar transiciones de estado alternativas para acomodar las diferentes longitudes posibles de una cadena semi-analizada. ^{[ 2 ]}

Los lenguajes libres de contexto deterministas pueden ser reconocidos por una máquina de Turing determinista en tiempo polinomial y espacio O (log ² n ); como corolario, DCFL es un subconjunto de la clase de complejidad SC . ^{[ 3 ]}

El conjunto de lenguajes libres de contexto deterministas es cerrado bajo las siguientes operaciones: ^{[ 4 ]}

• complementar
• homomorfismo inverso
• cociente correcto con un lenguaje regular
• pre: pre(${\displaystyle L}$) es el subconjunto de todas las cadenas que tienen un prefijo propio que también pertenece a${\displaystyle L}$.
• min: min(${\displaystyle L}$) es el subconjunto de todas las cadenas que no tienen un prefijo adecuado en${\displaystyle L}$.
• máximo: máximo(${\displaystyle L}$) es el subconjunto de todas las cadenas que no son el prefijo de una cadena más larga en${\displaystyle L}$.

El conjunto de lenguajes libres de contexto deterministas no es cerrado bajo las siguientes operaciones: ^{[ 4 ]}

• unión
• intersección
• concatenación
• Estrella Kleene
• morfismo libre de ε
• Imagen especular

Los lenguajes de esta clase tienen gran importancia práctica en la informática, ya que pueden analizarse de forma mucho más eficiente que los lenguajes libres de contexto no deterministas. La complejidad del programa y el tiempo de ejecución de un autómata de pila determinista es mucho menor que el de uno no determinista. En la implementación ingenua, este último debe hacer copias de la pila cada vez que ocurre un paso no determinista. El mejor algoritmo conocido para comprobar la pertenencia a cualquier lenguaje libre de contexto es el algoritmo de Valiant , que toma un tiempo ^de O( n²³⁷⁸ ), donde n es la longitud de la cadena. Por otro lado, los lenguajes libres de contexto deterministas pueden ser aceptados en un tiempo de O( n ) por un analizador LR( k ) . ^{[ 5 ]} Esto es muy importante para la traducción de lenguajes informáticos porque muchos lenguajes informáticos pertenecen a esta clase de lenguajes.

• lenguaje libre de contexto
• Autómata de pila determinista
• Gramática libre de contexto determinista
• Lenguaje determinista simple