Transcript
AMPLIACIÓN DE LENGUAJES FORMALES Y AUTÓMATAS CONTROL 22-01-2007 Apellidos:_______________________________________________ Nombre: _______________________________________________ TEST (3 puntos) Responda si los siguientes enunciados - precedidos por una letra - son verdaderos o falsos utilizando las tablas que figuran al final. Al rellenar la tabla, coloque una cruz en la fila V si considera que el enunciado de la correspondiente columna es verdadero. De forma excluyente, coloque una cruz en la fila F cuando considere que es falso. Las respuestas correctas sumarán 0.2 puntos, las incorrectas restarán 0.2 puntos y las respuestas en blanco no serán evaluadas. Manifieste nítidamente qué tabla considera su respuesta final, tachando completamente las demás tablas utilizadas. •
Sea un homomorfismo h(a)=“00” y h(b)=“0”. A. Sea G=({a,b},{S,B},S,{S→BBa,B→ab|ba}). Si L=L(G) entonces se tiene que H(L)={“00000000”} B. Para todo L⊆Σ* se cumple |L|≥|H(L)| C. Para todo L⊆Σ* se cumple |L|≤|H(L)| D. Para toda cadena u tal que u=h*(v) se cumple que |u|≥|v| E. Para toda cadena u tal que u=h*(v) se cumple que |u|≤|v| Sea M un AF=(Σ,Q,q0,F, δ) tal que L=L(M). Sean u,v dos cadenas de Σ* F. Si no existen dos estados distintos p,q∈Q tales que ∀z∈Σ* se cumple que δ*(p,z)∈F sii δ*(q,z)∈F, entonces u≡Lv sii u≡Mv G. Si u≡Mv entonces u≡Lv H. Si u≡Lv entonces u≡Mv I. Si u∈L y v∈L ⇒ u≡Lv J. Sea L1⊆Σ* y sean i,j dos números naturales. Si ai≡L1aj entonces L1 es regular Sobre el Teorema de Kleene K. Define un método de paso de expresiones regulares a AFD L. Define un método de paso de expresiones regulares a AF M. Define un método de paso de expresiones regulares a λ-AFND N. La expresión regular Rijk se define como Rijk = Rijk −1 + Rikk −1 ( Rkkk −1 ) * Rkjk −1 O. Utiliza los AF de Thompson que se caracterizan por tener un único estado final y por no tener arcos que terminan en el estado inicial ni salen del estado final
•
•
V F
A X
B X
C
D X
X
E
F X
G X
X
H
I
J
K
X
X
X
X
L X
M X
N
O X
X
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
V F
V F
AMPLIACIÓN DE LENGUAJES FORMALES Y AUTÓMATAS CONTROL 22-01-2007
Apellidos:_______________________________________________ Nombre: _______________________________________________
Ejercicio 1. (1 punto) Diseña una máquina secuencial de Moore que imprima en la cinta de salida la letra ‘p’ si la suma parcial de los dígitos introducidos es par, o la letra ‘i’ si es impar. La máquina sólo recibirá dígitos del 1 al 4 y tendrá una tecla ‘C’ que sirve de ‘reset’ (pone a 0 la suma). Podemos asumir que al iniciar o al pulsar la tecla ‘C’ la máquina imprimirá una p.
Solución:
MO 1 2 3 4 C →q0/p q1 q0 q1 q0 q0 q1/i q0 q1 q0 q1 q0
AMPLIACIÓN DE LENGUAJES FORMALES Y AUTÓMATAS CONTROL 22-01-2007 Apellidos:_______________________________________________ Nombre: _______________________________________________ Ejercicio 2. (1 punto) Escriba la función de transición del AP equivalente a la siguiente gramática. S → AAa A→ BbB B→ a Solución: δ(q, λ, S) = {(q, AAa)} δ(q, λ, A) = {(q, BbB)} δ(q, λ, B) = {(q, a)} δ(q, a, a) = {(q, λ)} δ(q, b, b) = {(q, λ)}
AMPLIACIÓN DE LENGUAJES FORMALES Y AUTÓMATAS CONTROL 22-01-2007 Apellidos:_______________________________________________ Nombre: _______________________________________________ Ejercicio 3 (2 puntos). Dada la gramática G=({a,b},{S,A,B},S,{ S → AAa, A → BbB, B → a}): a) Desarrolle el algoritmo CYK para la cadena “abaab”. b) Marque con un circulo las casillas que habría que reevaluar si cambiamos el último símbolo de la cadena del apartado a) (analizando la cadena “abaaa”). Escriba el nuevo valor para las casillas que hayan cambiado. c) ¿Pertenecen las cadenas “abaab” y “abaaa” a L(G)? (Razone su respuesta).
Solución:
Paso a FNC:
Lexicalización
Binarización
S → AACa A → BCbB B →a Ca → a Cb → b S → AD1 D1 → ACa A → BD2 D2 → CbB B →a Ca → a Cb → b
CYK: a) Tabla de análisis: j=i+4 j=i+3 j=i+2 j=i+1 j=i
D1 A B,Ca a
D2 Cb b
B,Ca a
B,Ca a
Cb b
b) La única casilla que cambia es la T[5,5]={B,Ca} (antes {Cb}). c) Ninguna de las dos cadenas pertenece al lenguaje ya que en ambos casos el axioma de la gramática NO está presente en la casilla T[1, 5], por lo que NO es capaz de derivar la cadena completa (desde la posición 1 hasta la 4).
AMPLIACIÓN DE LENGUAJES FORMALES Y AUTÓMATAS CONTROL 22-01-2007
Apellidos:_______________________________________________ Nombre: _______________________________________________ Ejercicio 4 (1 puntos). Mostrar la salida del siguiente programa en Perl: $_="[43] [abc] [410]"; print "1- $1\n" print "2- $1\n" print "3- $1\n" print "4- $1\n"
while /(\B\w\B)/g; if /(\d+)\D/; if /(\d+?)\D/; if /([\w+])/;
s/(\d+).*?(\d+)/$1+$2/eg; print "5- $_\n";
SOLUCIÖN:
112345-
b 1 43 43 4 [453]
AMPLIACIÓN DE LENGUAJES FORMALES Y AUTÓMATAS CONTROL 22-01-2007
Apellidos:_______________________________________________ Nombre: _______________________________________________ Ejercicio 5 (2 puntos). Un fichero de entrada contiene rangos formados por dos numeros naturales. Diseña un programa en Perl que identifique todos los rangos cuyos dos números coinciden en la ultima cifra (por ejemplo, [9-29]) y muestre por pantalla su diferencia. Ejemplo de entrada y salida
Entrada.in
Salida
[23-23] [12-4] [12-122] [35-5] [256-67] [10-0]
Rango Rango Rango Rango
[23-23] Diferencia:0 [12-122] Diferencia:-110 [35-5] Diferencia:30 [10-0] Diferencia:10
SOLUCIÓN $in="entrada.in"; open(IN,$in) or die("No puedo abrir $in\n"); while () { while (/(\[(\d*(\d))\-(\d*\2)\])/g) { "Rango $1 Diferencia:",$2-$4,"\n"; } } close(IN);