Este documento describe varias actividades relacionadas con gramáticas libres de contexto y autómatas de pila. En la primera actividad, se piden derivaciones para diferentes gramáticas. En la segunda, se demuestra que una cadena tiene dos árboles de derivación para una gramática ambigua. La tercera actividad pide derivaciones para una gramática que genera expresiones regulares. Las últimas actividades describen autómatas de pila deterministas para diferentes lenguajes.
0 calificaciones0% encontró este documento útil (0 votos)
43 vistas8 páginas
Este documento describe varias actividades relacionadas con gramáticas libres de contexto y autómatas de pila. En la primera actividad, se piden derivaciones para diferentes gramáticas. En la segunda, se demuestra que una cadena tiene dos árboles de derivación para una gramática ambigua. La tercera actividad pide derivaciones para una gramática que genera expresiones regulares. Las últimas actividades describen autómatas de pila deterministas para diferentes lenguajes.
Este documento describe varias actividades relacionadas con gramáticas libres de contexto y autómatas de pila. En la primera actividad, se piden derivaciones para diferentes gramáticas. En la segunda, se demuestra que una cadena tiene dos árboles de derivación para una gramática ambigua. La tercera actividad pide derivaciones para una gramática que genera expresiones regulares. Las últimas actividades describen autómatas de pila deterministas para diferentes lenguajes.
Este documento describe varias actividades relacionadas con gramáticas libres de contexto y autómatas de pila. En la primera actividad, se piden derivaciones para diferentes gramáticas. En la segunda, se demuestra que una cadena tiene dos árboles de derivación para una gramática ambigua. La tercera actividad pide derivaciones para una gramática que genera expresiones regulares. Las últimas actividades describen autómatas de pila deterministas para diferentes lenguajes.
Descargue como DOCX, PDF, TXT o lea en línea desde Scribd
Descargar como docx, pdf o txt
Está en la página 1/ 8
UNIVERSIDAD NACIONAL MAYOR DE SAN MARCOS
(Universidad del Perú, DECANA DE AMÉRICA)
FACULTAD DE INGENIERÍA DE SISTEMAS E
INFORMÁTICA
ASIGNATURA : Lenguajes y Compiladores
TRABAJO : Practica N° 4
PROFESOR : HUAPAYA CHUMPITAZ , Mario Agustin
INTEGRANTES :
● MARCA RIVERA, Braulio Jesús 18200327
● RODRÍGUEZ PORRAS, José David 18200330 ● MARCELO MACAVILCA, Luis 16200091
LIMA - PERÚ AÑO 2021 Actividades I) Desarrolle lo siguiente
a.
E => E+E E => I I => a E => I I => b
b.
E => E+E E => I E => I I => b I => a
2) Considere la gramática libre de contexto
S→aS | aSbS | λ Esta gramática es ambigua. Demuestre que la cadena aab tiene dos: a) Árboles de derivación. b) Derivaciones más a la izquierda. c) Derivaciones más a la derecha.
a) Árboles de derivación
b) Derivaciones más a la izquierda
S → aS → aaSbS → aaλbS → aabS → aabλ → aab
S → aSbS → aaSbS → aaλbS → aabS → aabλ → aab
c) Derivaciones más a la derecha
S → aS → aaSbS → aaSbλ → aaSb → aaλb → aab
S → aSbS → aSbλ → aSb → aaSb → aaλb → aab
3) La siguiente gramática libre de contexto genera el lenguaje de
expresiones regulares 0*1(0+1)*: S → A1B
A → 0A | λ B → 0B | 1B | λ
Obtener posibles derivaciones por la derecha y por la izquierda para las
siguientes cadenas: a. 00101 b. 1001 c. 00011 a. 00101
Por la izquierda: S → A1B → 0A1B → 00A1B → 001B → 0010B → 00101B → 00101 → 00101λ →00101
Por la derecha: S → A1B → A10B → A101B → A101 → 0A101 → 00A101 → 00λ101 → 00101
b. 1001
Por la izquierda: S → A1B → λ1B → 1B → 10B → 100B → 1001B → 1001λ → 1001
Por la derecha: S → A1B → A10B → A100B → A1001B → A1001λ → A1001 → λ1001 → 1001
c. 00011
Por la izquierda: S → A1B → 0A1B → 00A1B → 000A1B → 000λ1B → 0001B → 00011B →00011λ → 00011
Por la derecha: S → A1B → A11B → A11λ → A11 → 0A11 → 00A11 → 000A11 → 000λ11 → 00011
4) Diseñe un autómata a pila determinístico para el lenguaje: L=
❖ Estados q0, q1 ❖ Estado inicial q0 ❖ Estado final q1 ❖ Alfabeto de entrada _ = {a, b} ❖ Alfabeto de pila {a, b, Z0} Donde se define las siguientes reglas: ● La pila lleva la cuenta de número de as menos número de bs ● Si en la cima hay una b y leo una a desapilo ● Si en la cima hay una a y leo una b desapilo ● Si en la cima hay una a y leo una a apilo ● Si en la cima hay una b y leo una b apilo ● Si termino la entrada con la pila vacía acepto
Esencialmente el AP almacena en la pila el exceso de as sobre bs o viceversa. Cuando la pila está vacía las cantidades son iguales. Si no, la pila debería contener solo as o solo bs. La idea es que, cuando se recibe una a y en el tope de la pila hay una b, se “cancelan” consumiendo la a y desapilado la b, y viceversa. Cuando se reciba una a y en la pila haya exceso de as, se apila la nueva a, y lo mismo con b. El El problema es que debe ser posible apilar la nueva letra cuando la pila esta vacía. Como no puede expresarse el hecho de que la pila debe estar vacía.
