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.

Descripción

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 ]}

Propiedades

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( ) es el subconjunto de todas las cadenas que tienen un prefijo propio que también pertenece a . $L$ $L$
min: min( ) es el subconjunto de todas las cadenas que no tienen un prefijo adecuado en . $L$ $L$
max: max( ) es el subconjunto de todas las cadenas que no son el prefijo de una cadena más larga en . $L$ $L$

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

Importancia

The languages of this class have great practical importance in computer science as they can be parsed much more efficiently than nondeterministic context-free languages. The complexity of the program and execution time of a deterministic pushdown automaton is vastly less than that of a nondeterministic one. In the naive implementation, the latter must make copies of the stack every time a nondeterministic step occurs. The best known algorithm to test membership in any context-free language is Valiant's algorithm, taking O(n^2.378) time, where n is the length of the string. On the other hand, deterministic context-free languages can be accepted in O(n) time by an LR(k) parser.^[5] This is very important for computer language translation because many computer languages belong to this class of languages.

References

^Hopcroft, John; Jeffrey Ullman (1979). Introduction to automata theory, languages, and computation. Addison-Wesley. p. 233.
^Hopcroft, John; Rajeev Motwani; Jeffrey Ullman (2001). Introduction to automata theory, languages, and computation 2nd edition. Addison-Wesley. pp. 249–253.
^Cook, Stephen A. (April 30 – May 2, 1979). "Deterministic CFL's are accepted simultaneously in polynomial time and log squared space". Proceedings of the eleventh annual ACM Symposium on Theory of Computing - STOC '79. Atlanta. pp. 338–345. doi:10.1145/800135.804426.
^ ^a ^bHoogeboom, Hendrik; Engelfriet, Joost (2004). Formal Languages and Applications. Springer-Verlag Berlin Heidelberg. p. 128. ISBN 978-3-642-53554-3.
^Knuth, D. E. (July 1965). "On the translation of languages from left to right". Information and Control. 8 (6): 607–639. doi:10.1016/S0019-9958(65)90426-2.

[1] Hopcroft, John; Jeffrey Ullman (1979). Introduction to automata theory, languages, and computation. Addison-Wesley. p. 233.

[2] Hopcroft, John; Rajeev Motwani; Jeffrey Ullman (2001). Introduction to automata theory, languages, and computation 2nd edition. Addison-Wesley. pp. 249–253.

[3] Cook, Stephen A. (April 30 – May 2, 1979). "Deterministic CFL's are accepted simultaneously in polynomial time and log squared space". Proceedings of the eleventh annual ACM Symposium on Theory of Computing - STOC '79. Atlanta. pp. 338–345. doi:10.1145/800135.804426.

[Formal_Languages_and_Applications-4] Hoogeboom, Hendrik; Engelfriet, Joost (2004). Formal Languages and Applications. Springer-Verlag Berlin Heidelberg. p. 128. ISBN 978-3-642-53554-3.

[5] Knuth, D. E. (July 1965). "On the translation of languages from left to right". Information and Control. 8 (6): 607–639. doi:10.1016/S0019-9958(65)90426-2.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[5]

Descripción

Propiedades

Importancia

See also

References