Advertencia: no has iniciado sesión. Tu dirección IP se hará pública si haces cualquier edición. Si
inicias sesión o
creas una cuenta, tus ediciones se atribuirán a tu nombre de usuario, además de otros beneficios.
Puedes deshacer la edición.
Antes de deshacer la edición, comprueba la siguiente comparación para verificar que realmente es lo que quieres hacer, y entonces publica los cambios para así efectuar la reversión.
Revisión actual |
Tu texto |
Línea 82: |
Línea 82: |
|
| |
|
| Fijar un conjunto de estados Q de 4 estados y un alfabeto <math>\Sigma</math> de dos símbolos, dar la cantidad de autómatas finitos deterministicos de esta clase. | | Fijar un conjunto de estados Q de 4 estados y un alfabeto <math>\Sigma</math> de dos símbolos, dar la cantidad de autómatas finitos deterministicos de esta clase. |
|
| |
| 7) Sea G = (N, T, P, S) una gramática libre de contexto, no recursiva a izquierda y sin producciones A-> lambda. Existe una constante c tal que para todo par de símbolos no-terminales A,B, y para toda expresión α, si A => Bα entonces esta derivación se hace en una cantidad de pasos menor que c.
| |
| (Adaptación del Lema 4.1 Aho-Ullman vol. 1).
| |
| Ayuda: Este resultado se ua en la demostración de complejdida del algoritmo LL.Sea G = (N, T, P, S) una gramática libre de contexto, no recursiva a izquierda y sin producciones A-> lambda. Existe una constante c tal que para todo par de símbolos no-terminales A,B, y para toda expresión α, si A => Bα entonces esta derivación se hace en una cantidad de pasos menor que c.
| |
| (Adaptación del Lema 4.1 Aho-Ullman vol. 1).
| |
| Ayuda: Este resultado se ua en la demostración de complejdida del algoritmo LL.
| |