AMPLIACIÓN DE LENGUAJES FORMALES Y AUTÓMATAS BOLETÍN DE PROBLEMAS








AMPLIACIÓN DE LENGUAJES FORMALES Y AUTÓMATAS

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:

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:

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:

Los siguientes tres ejemplos son representaciones textuales de árboles:

____________________________________________________________________________________

Conteste de forma razonada las siguientes preguntas:

_____________________________________________________________________________________

Aplique el método LL(1) a las siguientes gramáticas:

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:

_____________________________________________________________________________________

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.

__________________________________________________________________________________

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:

_____________________________________________________________________________________

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:

_____________________________________________________________________________________

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:

_____________________________________________________________________________________

Demuestre, aplicando el método CYK y Earley, si son ciertas las siguientes aseveraciones:






Tags: ampliación de, autómatas, formales, lenguajes, boletín, ampliación, problemas