En teoría lenguaje formal , lenguajes libres de contexto deterministas ( DCFL ) son un subconjunto propio de los lenguajes libres de contexto . Son los lenguajes libres de contexto que pueden ser aceptados por un autómata pushdown determinista . Los DCFL siempre son inequívocos, lo que significa que admiten una gramática inequívoca . Hay CFL inequívocas no deterministas, por lo que las DCFL forman un subconjunto adecuado de CFL inequívocas.
Los DCFL son de gran interés práctico, ya que se pueden analizar en tiempo lineal, y varias formas restringidas de DCFG admiten analizadores sintácticos prácticos simples. Por tanto, se utilizan ampliamente en todas las ciencias de la computación.
La noción de DCFL está estrechamente relacionada con el autómata de empuje determinista (DPDA). Es donde el poder del lenguaje de los autómatas de empuje se reduce si los hacemos deterministas; los autómatas de empuje se vuelven incapaces de elegir entre diferentes alternativas de transición de estado y, como consecuencia, no pueden reconocer todos los lenguajes libres de contexto. [1] Las gramáticas inequívocas no siempre generan un DCFL. Por ejemplo, el lenguaje de palíndromos de longitud uniformeen el alfabeto de 0 y 1 tiene la gramática libre de contexto inequívoca S → 0S0 | 1S1 | ε. Una cadena arbitraria de este lenguaje no se puede analizar sin leer primero todas sus letras, lo que significa que un autómata pushdown tiene que probar transiciones de estado alternativas para adaptarse a las diferentes longitudes posibles de una cadena semi-analizada. [2]
Los lenguajes deterministas libres de contexto pueden ser reconocidos por una máquina de Turing determinista en tiempo polinomial y espacio O (log 2 n ); como corolario, DCFL es un subconjunto de la clase de complejidad SC . [3]
Los lenguajes de esta clase tienen una gran importancia práctica en informática, ya que se pueden analizar de forma mucho más eficiente que los lenguajes no deterministas libres de contexto. La complejidad del programa y el tiempo de ejecución de un autómata pushdown determinista es mucho menor que la 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 algoritmo más conocido para probar la pertenencia a cualquier lenguaje sin contexto es el algoritmo de Valiant , que toma O ( n 2.378 ) tiempo, donde n es la longitud de la cadena. Por otro lado, los lenguajes deterministas libres de contexto pueden ser aceptados en tiempo 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.