Documento

Ejercitario de Repaso
1) a) Dada la siguiente expresión regular, construye el diagrama de estados del AF D optimizado
a (1 2* | 1 3 2*) | a b 2 *
b) Dada la siguiente expresión regular : ( a( 1+t*1 | 1 a) | a t+1*a)t* . Grafica el diagrama de estados del autómata que reconoce este lenguaje y luego construye la matriz de transiciones del autómata determinista optimizado que reconoceeste lenguaje.

2) Demuestra que el siguiente lenguaje: L = {12bc,1212bbc, 121212bbbc,12121212bbbbc,…}, no es regular.
3)Dada la siguiente gramática libre de Contexto: G(P)
P:{ P P S | S |P f VT={f , v, (, ), n, e, *}
S T v | T v ( n )
T e | f | * e | * f
}
Gráfica el árbol sintáctico descendente y ascendente, para la sentencia : f v * f v ( n )
4) Convierte lasiguiente gramática a la forma normal de Chomsky: 3p
G(Z)
P:{ Vt= {m,a,d} Vn={Z,P,R}
Z m P a | a R
P R d m | a m
R m a P | d m a
}
5) Dada la siguiente gramática libre de Contexto:G(N)
P:{ N N D | Q + | N a VT={+ , a, b, p, -} VN = {N, D, Q}
D b | + b | - p | p
Q D b | D a + p b | Q a
}
a) Desarrolla el árbol sintáctico ascendente, y su secuenciade derivación para la sentencia : p a + p b + - p indicando claramente el orden de su construcción.
b) Convierte la gramática a la forma Normal de Greibach.
c) Diseña el diagrama deestados de su autómata de pila por vaciado.

6) Dada la siguiente gramática libre de Contexto: G(S)
P:{ S input var | S print R VT={input, var, print, +, -, *, num, (, )}
R R + T | R – T |T
T T * P | P
P num | var | ( R )
}
a) Convierte la gramática a la Forma Normal de Chomsky.
b) Convierte la GLC a la Forma Normal de Greibach.
c) Grafica el diagramade estados, con todos los datos incluidos, del autómata de Pila por Vaciado, que reconozca el lenguaje generado por esta gramática.

7-Considerando el siguiente diagrama de estados de un autómata...