Escuela Politécnica de Ingeniería de Gijón
PROBLEMAS DE GRAMÁTICAS (2013-2014)- Sesión 10 Gramáticas Regulares 1. Hallar la gramática que genera el lenguaje reconocido por el siguiente autómata: 1 1 0 1 0 0 A B C 1 D E 0 0
1 2. Determinar una GR que genere el lenguaje L((ab* + ba*) bab*). 3. Construir el autómata que reconoce el lenguaje generado por la siguiente gramática: G = (VT, VN, S, P) VT = {0, 1} VN = {S, A, B, C} P:{ S::= 1B 1C A::= 1B 1C B::= 0A C::= } 4. Determinar una GLC que genere las cadenas de 0’s y 1’s cuyo penúltimo símbolo es un 0. Construir otra gramática que genere las cadenas de 0’s y 1’s cuyo penúltimo símbolo NO es un 0. (véase boletín de la sesión 7)
Grámaticas Libres de Contexto 5. Encontrar el lenguaje generado por la gramática G = (V, T, P, S) dada por: V = {S, M, N}, T = {x,y,z}, P = { S MzN M xM | N yN | } ¿De qué tipo son la gramática y el lenguaje generado por ella? Dar una derivación más a la derecha y un árbol de derivación para la palabra xxzy 6. Hallar una GLC que genere L = {
R
/
{0, 1}*}
7. Construir una gramática que genere el lenguaje L = {ai bj ci+2j | i,j 0}. Dar una derivación más a la izquierda y un árbol de derivación para las palabras abccc y bbcccc 8. Encontrar el lenguaje generado por la gramática G = ({S,X,Y}, {a, b}, P, S) donde P es: P={ S X Y
XY aXb | Yb aY | }
1