AMPLIACIÓN DE LENGUAJES FORMALES Y AUTÓMATAS
Boletín de Problemas
_____________________________________________________________________________________
Dados los siguientes atributos h, s: entero asociados a todos los símbolos no terminales de la siguiente gramática, y considerando la siguiente atribución:
S X Y Z { Z.h:= S.h; X.h :=Z.s; S.s:=X.h –2; Y.h := S.s;}
X a {X.s:=2*X.h;}
<¿Qué efecto tendría sustituir la instrucción Z.h := S.h por la instrucción Z.h:=S.s?
____________________________________________________________________________________
Defina una gramática atribuida que indique si una entrada pertenece al lenguaje dependiente del contexto descrito por {ww | w es una palabra del lenguaje (a+b)*}
_____________________________________________________________________________________
Defina una gramática atribuida que, dado un TAD árbol, construya el árbol de derivación para una palabra que pertenezca al lenguaje independiente del contexto {an bn | n 0}
_____________________________________________________________________________________
Defina una gramática atribuida que, dada una matriz descrita por filas, compruebe si cada una de las filas contiene el mismo número de columnas. Tanto la matriz completa como cada una de sus filas estarán delimitadas por paréntesis. Tanto las filas como los componentes de las columnas estarán separados por comas. Ejemplos:
((1,2),(2,3,4)) sería una matriz incorrecta
((1,1,1,1),(2,3,4,5),(2,3,4,6)) sería una matriz correcta
_____________________________________________________________________________________
Defina una gramática atribuida para la ejecución de un programa en el que se detallan operaciones donde intervienen matrices cuadradas de números enteros con rango 2x2. Todas las instrucciones del programa tendrán la siguiente forma:
identificador := expresión ;
El identificador asociará un nombre a una matriz. La expresión será una de las siguientes:
Un literal matriz de la forma ((n11, n12), (n21, n22 )) donde n11, n12, n21, y n22 son enteros.
Un identificador de matriz (similar al anteriormente indicado).
Una composición bien construida de operandos (identificadores o literales) y operaciones de suma y producto de matrices.
La expresión podrá hacer uso de paréntesis para establecer la prioridad de las operaciones. Para cada instrucción se mostrará el valor otorgado por la expresión al identificador. Téngase en cuenta que el valor de un identificador de matriz se corresponde con el último que le fue atribuido y que todos los identificadores que participen en las expresiones presentan un valor conocido. Por ejemplo:
Entrada:
A := ((1,0),(0,1)) ;
B := ((2,2),(2,3));
C := A+B;
C := (A*C)*A;
Salida:
>> A es ((1,0),(0,1))
>> B es ((2,2),(2,3))
>> C es ((3,2),(2,3))
>> C es ((3,2),(3,2))
(Nota: Defina un TAD matriz 2x2 de enteros donde se recogerán las operaciones utilizadas en la atribución ) _____________________________________________________________________________________
Defina una gramática atribuida que, haciendo uso de un TAD árbol binario, construya a partir de una expresión regular un árbol binario donde se representa dicha expresión. La expresión se definirá tan sólo mediante los operadores de unión, concatenación y cierre. La expresión podrá hacer uso de paréntesis para establecer la prioridad de las operaciones.
_____________________________________________________________________________________
Defina una gramática atribuida que, dada una expresión regular en la que intervienen tanto los operadores clásicos de unión, cierre de Kleene y concatenación como los operadores extendidos de cierre positivo a+ y opción a?, obtenga su expresión regular equivalente donde los operadores extendidos han sido convertidos en expresiones regulares donde intervienen tan sólo operadores clásicos. La expresión regular de entrada podrá hacer uso de paréntesis para establecer la prioridad de las operaciones.
_____________________________________________________________________________________
Sea ER una expresión regular definida sobre un alfabeto . La derivada de la expresión regular ER respecto a un símbolo a, denotada mediante Da (ER) se define de la siguiente forma:
Da () =
Da () =
Da (a) =
Da (b) = para todo b tal que b a
Da (+) = Da () + Da ()
Da () = Da () + d() Da () donde d()= si y d()= en otro caso
Da (*) = Da ()*
Dada una expresión regular ER, terminada en punto y coma, y seguida de un símbolo a, defina una gramática atribuida que obtenga Da (ER).
_____________________________________________________________________________________
Defina una gramática atribuida que, dada una primera secuencia etiquetada de polinomios con una sola incógnita x seguida de una segunda secuencia de posibles valoraciones de x para alguno de los polinomios anteriores, calcule sucesivamente e imprima el resultado obtenido al sustituir el valor de x en el polinomio. Un ejemplo sería el siguiente:
Entrada:
P1 3x +1;
P2 x^2+1;
P1 x=1;
P2 x=0;
P2 x=3;
Salida:
Para x=1 el polinomio P1 vale 4
Para x=0 el polinomio P2 vale 1
Para x=3 el polinomio P2 vale 10
(Nota: Defina un TAD polinomio donde se recojan las operaciones necesarias para la atribución).
____________________________________________________________________________________
Defina una gramática atribuida que transforme un árbol representado de forma textual en un árbol de tipo TAD árbol. La representación textual de un árbol se define de la siguiente forma:
La representación textual de un nodo hoja a será mediante el propio símbolo a
Si A es un nodo interior que domina los k subárboles B1, B2, .., Bk , su representación textual será de la forma A( B1’ B2’ ... Bk’ ) donde B’ es la representación textual del subárbol B.
Los siguientes tres ejemplos son representaciones textuales de árboles:
S(a S(b S(e) c) d)
S(a)
A(B(b) C(b) d e)
____________________________________________________________________________________
Conteste de forma razonada las siguientes preguntas:
¿ Puede existir un atributo que sea a la vez heredado y sintetizado?
¿ Reconocen la misma clase de lenguajes los autómatas de pila ascendentes y descendentes?
¿ Porqué son deterministas los lenguajes reconocidos por el método LL(1)?
¿ Tendría sentido asociar un atributo heredado a los símbolos terminales?
Si atribuimos una gramática independiente del contexto, ¿necesariamente reconocerá un lenguaje dependiente del contexto?
_____________________________________________________________________________________
Aplique el método LL(1) a las siguientes gramáticas:
{ S E$ , E aAbE | bBaE | , A aAbA | , B bBaB | }
{ S Sb | b | bA , S a | }
{ S AB , A aA | b , B b | }
{ S Ea | ES , E ES | b }
{ S aSA | ab | ac , A b | c }
{ S aSb | aSbb | }
{E E + T | T , T T*F | F , F (E) | num }
En el caso de que alguna de ellas sea una gramática LL(1), simule el comportamiento del método para varias palabras que pertenezcan al lenguaje generado por dicha gramática.
_____________________________________________________________________________________
Calcule los conjuntos PRIMERO y SIGUIENTE para cada uno de los símbolos no terminales de las siguientes gramáticas:
{ S AB , A Aa | , B bB | }
{ S AB , A Aa | , B b }
{ S ABC , A Aa | , B bB | , C Cc | c }
{ S Ba | c , B bSd | }
_____________________________________________________________________________________
Defina un algoritmo que dada una gramática independiente del contexto G=(VT, VN, S, P) y un símbolo no terminal X VN calcule el conjunto SIGUIENTE(X).
_____________________________________________________________________________________
Defina un algoritmo que dada una gramática independiente del contexto G=(VT, VN, S, P), calcule el conjunto PRIMERO() para una secuencia de símbolos V*, siendo V= VT VN,.
_____________________________________________________________________________________
Dadas las siguientes gramáticas encontrar una constante k de forma que el método LL(k) sea aplicable.
{ S Ac , A aB | BBb , B b | ab}
{ S aAbB | bAbB , A ab | a , B aB | b}
__________________________________________________________________________________
Dado el siguiente lenguaje L={an | n 0} {anbn | n 0}. ¿Existe alguna constante k de forma que el lenguaje sea reconocido por el método LL(k) ?
____________________________________________________________________________________
Pruebe que la unión, concatenación, cierre de Kleene, intersección y complementación de lenguajes regulares son operaciones cerradas.
_____________________________________________________________________________________
Dados dos autómatas finitos deterministas M1 y M2, defina un nuevo autómata finito determinista M3 que acepte al menos una palabra si y sólo si L(M1) L(M2). Podemos observar que el autómata M3 puede ser utilizado para decidir si dos autómatas finitos son equivalentes.
(Nota: Para la definición de M3 téngase en cuenta que todo lenguaje regular puede ser reconocido por un autómata finito determinista y que las operaciones de intersección, unión y complementación son cerradas para la clase de lenguajes regulares).
_____________________________________________________________________________________
Dado dos autómatas finitos deterministas: M1=(, Q1, q1, F1, 1) y M2=(, Q2, q2, F2, 2), podemos construir otro autómata finito M3=(, Q1 x Q2, [q1,q2], F1 x F2, ) cuya función de transición se define:
: (Q1 x Q2) x (Q1 x Q2) tal que
([p1,p2],a)=[ 1(p1,a), 2(p2,a)]
¿Qué relación existe entre los lenguajes reconocidos por los autómatas M1, M2 y M3?
(Nota: El par [p,q] representa un elemento del producto cartesiano PxQ)
_____________________________________________________________________________________
Defina sustituciones u homomorfismos que justifiquen la relación entre los siguientes lenguajes:
Si 0*1* es regular entonces an con n 0 es regular
Si 1*0*+0* es regular entonces (a+b)* es regular
Si 1*+0* es regular entonces (ab)* es regular
Si 1*(1+0)* es regular entonces (aab)*(aab(b+))* es regular
Si (0*1*)* es regular entonces (ab+cd)* es regular
_____________________________________________________________________________________
Dado los autómatas finitos deterministas M1 y M2 definidos de forma tabular, encontrar palabras que justifiquen si reconocen lenguajes regulares vacíos o infinitos.
M1 |
a |
*q0 |
q0 |
M2 |
a |
b |
q0 |
q1 |
q2 |
q1 |
q2 |
q3 |
q2 |
q2 |
q2 |
*q3 |
q2 |
q2 |
____________________________________________________________________________________
Discuta qué está mal en el siguiente razonamiento. Sabemos que cada uno de los siguientes conjuntos:
{}, {ab},{aabb},{aaabbb}, ....
son lenguajes regulares. Puesto que la unión de lenguajes regulares es un lenguaje regular, aplicando este resultado sobre los lenguajes anteriores llegamos a la conclusión de que también será regular el lenguaje definido como {an bn | n 0}.
_____________________________________________________________________________________
Justifique que está mal en el siguiente razonamiento. Sabemos que el lenguaje L={0n | n > 0} es regular y que la sustitución de lenguajes regulares es una operación cerrada. Puesto que {an | n > 0} es un lenguaje regular, aplicando la sustitución f(0)= an , tendríamos que {(an)n | n > 0} es un lenguaje regular.
_____________________________________________________________________________________
Obtenga la forma normal de Greibach para las siguientes gramáticas:
{ S AB | CA , A a , B BC | AB , C aB | b }
{ S aAb | a , A SS | b }
{ S AB | BC , A AB | a , B AA | CB | b , C a | b }
{ S aB | aaB , A , B bA | }
_____________________________________________________________________________________
Pruebe que la unión, concatenación y cierre de Kleene de lenguajes independientes del contexto son operaciones cerradas.
_____________________________________________________________________________________
Dada una gramática independientes del contexto G=( VT, VN, S, P) y, considerando definida una gramática independiente del contexto Ga =( VaT, VaN, Sa, Pa) para cada símbolo terminal a VT, defina la gramática independiente del contexto resultante de aplicar la sustitución f(a)= Ga para cada a VT.
_____________________________________________________________________________________
Pruebe con un contraejemplo que la intersección de lenguajes independientes del contexto no es una operación cerrada. Apoyándose en el resultado anterior demuestre que la complementación de lenguajes independientes del contexto tampoco es una operación cerrada.
_____________________________________________________________________________________
Sea una gramática independiente del contexto G=(VT, VN, S, P) en forma normal de Chomsky en la que, dado un símbolo A VN y una cadena w VT+, se tiene que A * w. Considerando que T es el árbol de análisis para la derivación anterior, pruebe que si la profundidad de T es n, entonces |w| 2n-1.
_____________________________________________________________________________________
Demuestre, aplicando el lema del bombeo, los siguientes enunciados:
{ anbn | n 0} no es regular
{akbaj | kj y k,j >0 } no es regular
{xk+jykzk | k0 y m1} no es regular
{(a+b+c)* | con igual número de símbolos a, b y c} no es independiente del contexto
{akbj | j>0 y j=k2 } no es independiente del contexto
_____________________________________________________________________________________
Demuestre, aplicando el método CYK y Earley, si son ciertas las siguientes aseveraciones:
La palabra aabb es reconocida por la gramática { S aSb | ab }
La palabra aa es reconocida por la gramática { S SS | a }
La palabra bb es reconocida por la gramática { S AB , A aA | , B Bb | b }
Tags: ampliación de, autómatas, formales, lenguajes, boletín, ampliación, problemas