Escuela Politécnica de Ingeniería de Gijón
PROBLEMAS DE GRAMÁTICAS (2013-2014)- Sesión 12 1. Simplificar la gramática siguiente y determinar su forma normal de Chomsky G = ({S, A, B, C, D, E, F}, {a, b}, S, P) dónde P = { S FaA | aAb | Bb A CD | a | S B ACD | b C | AC D | aFE E bF | }
2. Dada la siguiente gramática G = ({S,A,B,C,D}, {a,b}, S, P) donde P = { S aAa | Caa | bAb | DaC A aSa | CC | bSb B ab | DC | aBb C BbD | D CaD | BDb } Simplificar la gramática y determinar L(G). Posteriormente, determinar su forma normal de Chomsky. A continuación, determinar la pertenencia a L(G) de abaaba mediante el algoritmo CYK y mediante una derivación más a la izquierda.
3. Sea G = ( V, T, S, P) una G.L.C. donde V = { S, A, B, C, D, E }; T = {a, b}; P = { S CASB | C A aAb | B bBa | CDA | ba C | aDE D aD | CDa E ab | ba } Demostrar que la cadena abba pertenece a L(G) mediante un árbol de derivación y mediante el algoritmo CYK
4. Construir la gramática libre de contexto generadora del siguiente lenguaje L = {0m 1n / m, n > 0; con m par y n impar ó viceversa} Demostrar que la cadena 001 pertenece a L(G) mediante una derivación más a la izquierda y mediante el algoritmo CYK
5. Sea L = {ai bj aj / posee i a’s, i, j 0}. Determínese una GLC que genere dicho lenguaje. Demostrar que la cadena abab pertenece a L(G) mediante una derivación más a la derecha y mediante el algoritmo CYK.
1
Escuela Politécnica de Ingeniería de Gijón
6. Considérese el lenguaje formal: L1 = {1 a 2 b / 1, 2 {a, b}*, |1| =|2|}, y la gramática G2 = ({S, A, B, C, D}, {0,1}, S, P) cuyo conjunto de producciones es: P = { S 0 C | B | 1D | A1S|B B0S C1A D0B } a) Describir de alguna forma L(G2) y calcular una gramática G3 generadora del lenguaje formado a partir de la concatenación de L1 con L(G2). b) Sea ahora = babb0 una palabra perteneciente a L(G3). Dar un árbol de derivación cuya producción sea .
7. Dada la G.L.C. G = ({S, A, B, C, D, E, F, G}, {a, b}, S, P) donde P = { S AB | BCB A FG | DE B C BB | DaE | a D a | Ea | cD Fb G a} Se pide calcular, el lenguaje que genera, la F.N.C. sin símbolos inútiles. 8. Sea X = {a, b, c}. Determínese una Gramática Libre de Contexto que genere el lenguaje sobre X L = {ai bj ck / i, k 0, j 1, k = 2j ó k = 2i}
9. Dada la gramática G definida por el conjunto de producciones siguiente, se pide decidir la pertenencia de la palabra abbaa al lenguaje generado por G, mediante el algoritmo CYK. P = { S AB | BC A AB | a B AA | CB | b Ca|b }
2