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 de empuje 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 pueden analizarse en tiempo lineal, y varias formas restringidas de DCFG admiten analizadores sintácticos sencillos y prácticos. Por tanto, se utilizan ampliamente en todas las ciencias de la computación.
Descripció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 pares en 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]
Propiedades
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]
El conjunto de lenguajes deterministas libres de contexto se cierra con las siguientes operaciones: [4]
- complemento
- homomorfismo inverso
- cociente correcto con un idioma regular
- pre: pre () es el subconjunto de todas las cadenas que tienen un prefijo adecuado que también pertenece a .
- min: min () es el subconjunto de todas las cadenas que no tienen un prefijo adecuado en .
- max: max () es el subconjunto de todas las cadenas que no son el prefijo de una cadena más larga en .
El conjunto de lenguaje determinista libre de contexto no se cierra con las siguientes operaciones: [4]
Importancia
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 ) mediante un analizador sintáctico 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.
Ver también
Referencias
- ^ Hopcroft, John ; Jeffrey Ullman (1979). Introducción a la teoría de autómatas, lenguajes y computación . Addison-Wesley. pag. 233.
- ^ Hopcroft, John ; Rajeev Motwani ; Jeffrey Ullman (2001). Introducción a la teoría de autómatas, lenguajes y computación 2ª edición . Addison-Wesley. págs. 249-253.
- ^ Cook, Stephen A. (30 de abril - 2 de mayo de 1979). "Las lámparas fluorescentes compactas deterministas se aceptan simultáneamente en tiempo polinomial y espacio logarítmico al cuadrado". Actas del undécimo simposio anual de ACM sobre teoría de la computación - STOC '79 . Atlanta. págs. 338–345. doi : 10.1145 / 800135.804426 .
- ^ a b Hoogeboom, Hendrik; Engelfriet, Joost (2004). Idiomas y aplicaciones formales . Springer-Verlag Berlín Heidelberg. pag. 128. ISBN 978-3-642-53554-3.
- ^ Knuth, DE (julio de 1965). "Sobre la traducción de idiomas de izquierda a derecha" (PDF) . Información y control . 8 (6): 607–639. doi : 10.1016 / S0019-9958 (65) 90426-2 . Archivado desde el original (PDF) el 15 de marzo de 2012 . Consultado el 29 de mayo de 2011 .