Taller GIC

UNIVERSIDAD DE CALDAS
FACULTAD DE INGENIERÍA
PROGRAMA DE INGENIERÍA DE SISTEMAS Y COMPUTACIÓN
ESTRUCTURA DE LENGUAJES
TALLER GRAMATICAS INDEPENDIENTES DELCONTEXTO
15/04/2013
Para entregar o enviar al correo rgarciatrabajos@gmail.com individual para la próxima clase,
dependiendo del grupo al que asista.
1.Cree Gramáticas Independientes del Contexto para los siguientes lenguajes
a. El conjunto de todas las cadenas de símbolos 0 y 1 tales que todo 0 va seguidoinmediatamente de al menos un 1
b. Las cadenas de símbolos 0 y 1 con un número igual de 0 y 1.
c. Las cadenas de símbolos 0 y 1 de la forma 00..0011..11 connúmero igual de 0 y de
1.
d. Las cadenas de símbolos de 0 y 1 que solo generan números capicúa (se leen igual
de derecha a izquierda que de izquierda aderecha).
2. Dadas las siguientes gramáticas
a. R  R”|”R
El símbolo “|” significa el operador “o” de las expresiones regulares
R RR
Concatenación
RR*Cerradura de Kleene
R R+
Cerradura positiva
R R?
Cero o una presencias de
R(R)
Ra|b
b. S
C
B
A
C

 A | aBa | AbA
 aA |Aa | Є
 bB |Bb | BC
aBaD |SBBb
 CB | CA | b

a) Quitar la recursividad por la izquierda de estas gramáticas
b) Factorizar por la izquierda las gramáticas
Nota: Recuerde que larecursividad por izquierda puede ser en cero o más pasos.
3. Para la gramática resultante del punto 2a calcular el conjunto primero, el conjunto siguiente,la tabla de análisis sintáctico y hacer el análisis sintáctico, mostrando la pila, la cadena y la
salida de la entrada ((a|b)*|b+(ab)?)+

Ruben Garcia.