Resumen

CAPITULO 10

LENGUAJES DETERMINISTICOS LIBRES DE CONTEXTO

En los extremos de la jerarquía, las maquinas (autómatas finitos y máquinas de Turing) no muestran diferencia alguna en su capacidad deaceptación, entre sus modelos determinísticos y no determinísticos. Para los autómatas de pila los PDAs aceptan una familia de lenguajes, los lenguajes determinísticos libres de contexto (DCFLs), quese encuentran propiamente entre los conjuntos regulares y los lenguajes libres de contexto.

FORMAS NORMALES PARA DPDAs

Un PDA es determinístico si:* Siempre que sea no vacía para alguna en , entonces
es vacío.

* Para cada encontiene cuando mucho un elemento.

Podemos poner a los DPDAs en una forma natural en donde las únicas operaciones de pila consisten en borrar el símbolo de la cima o insertar un símbolo:

*El DPDA no necesita nunca colocar más de un símbolo por movimiento, ya que puede colocar una cadena de símbolos uno a la vez, utilizando movimientos ϵ.

* Los DPDAs no necesitan nunca cambiar elsímbolo del tope de la pila. Los cambios se invitan mediante el almacenamiento del símbolo en el tope de la pila en el control finito y registrando los cambios que se hacen ahí.

COMO FORZAR A LOSDPDAs A BARRER SU PROPIA ENTRADA

* Sea M un DPDA. Existe un DPDA equivalente M tal que sobre cada entrada, M barre a la entrada completa.

Cerradura y complementación

* El complemento deun DCFL es un DCFL.

Cada CFL determinístico es aceptado por algún DPDA que, en un estado de aceptación, puedo no hacer ningún movimiento sobre la entrada ϵ.
GRAMATICAS LR (0)

Esta clase degramática es la primera de una familia que se conoce de manera colectiva como gramáticas LR.
LR (0) significa “barrido de izquierda a derecha” de la entrada produciéndose una derivación derecha y...