Examenes resueltos alfa

AMPLIACIÓN DE LENGUAJES FORMALES Y AUTÓMATAS 2ª CONVOCATORIA 07-09-09 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 siconsidera 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.

A. B. C.D. E. F. G. H. I. J.

• Respecto a las relaciones de equivalencia sobre cadenas de lenguajes

La relación “contiene la subcadena bc” es invariante por la derecha Si la relación ≡L no es de índice finito, el lenguaje L no es regular Si la relación ≡L no es de índice finito, el lenguaje L es independiente del contexto SI L es un lenguaje finito, la relación ≡L es de índice finito Si L es unlenguaje infinito, la relación ≡L no es de índice finito Sean u,v,w∈Σ* tales que ∈ , entonces ∈ ≥0 Sean u,v,w∈Σ* tales que ∈ | |≥ , entonces ∈ Sean u,v,w∈Σ* tales que ∈ ≥0, | |≥ Si Q=F={q0,q1}. Entonces q0 y q1 son equivalentes Si Q=F={q0,q1}. Entonces q0 y q1 no son equivalentes

• Sea
el
AFD
mínimo
M=(Σ,Q,q0,F,δ)

y
sea
n=|Q|
≥0

•Sea
M=(Σ,Q,q0,F,δ)
un
AFD
obtenido
tras
determinizar
un
λ‐AFND
M'=(Σ,Q',q'0,F',δ')

K. L. M. N. O. El número de estados de M es siempre superior al número de estados de M' Si el número de estads de M es igual al número de estados de M', entonces M es mínimo Sea L=L(M) y L'=L(M'). Se verifica que ≡L es igual que ≡ δ'({p1,...,pk},a)=λ*(δ(p1,a) ∪ … ∪ δ(pk,a)) {p1,...,pk}∈ ó p1,...,pk ∈

Solución: A V F X B X X C D X X X X X X E F G H I J X X X K L M X N X X O

A V F

B

CD

E

F

G

H

I

J

K

L

M

N

O

A V F

B

C

D

E

F

G

H

I

J

K

L

M

N

O

AMPLIACIÓN DE LENGUAJES FORMALES Y AUTÓMATAS 2ª CONVOCATORIA 07-09-09 Apellidos:_______________________________________________ Nombre: _______________________________________________
EJERCICIO 1 (2 puntos). Sea M el siguiente autómata de células deMcCulloch-Pitts Células c0 [p,0] [p,1] [q,0] [q,1] [s,0] [s,1] cF • Entradas < 0 r0 r[q,0] r[s,0] 1 r0 r[q,0] r[s,0] 0 r[p,1] 1 r[p,1] 0 r[p,0] r[q,1] r[s,1] 1 r[p,0] r[q,1] r[s,1] > r[p,0] r[q,1] r[s,1] Umbral 1 2 2 2 2 2 2 2 Salida r0 r[p,0] r[p,1] r[q,0] r[q,1] r[s,0] r[s,1] r

• •

Obtenga el AFD equivalente al autómata anterior Calcule R213 (a partir del Teorema de Kleene) considerando que elestado final ha sido numerado como 3. Sea L=1*, obtenga una expresión regular simplificada para L ∩ L(M)

SOLUCIÓN: AFD
→p

q *s
R213= 0+1(01)*(1+00) L ∩ L(M) = 111*

0 s p p

1 q s s

AMPLIACIÓN DE LENGUAJES FORMALES Y AUTÓMATAS 2ª CONVOCATORIA 07-09-09 Apellidos:____________________________________________ Nombre: _______________________________________________
EJERCICIO 2 (2 puntos).Sea la siguiente GIC G obtenida al transformar un AP M con aceptación por pila vacía. S → [pZ0p] | [pZ0q] [pZ0p] → a[pAp][pZ0p] | a[pAq][qZ0p] | b[pZ0p] [pZ0q] → a[pAq][qZ0q] | a[pAp][pZ0q] | b[pZ0q] | c [pAp] → b[pAp] | a [pAq] → b[pAq] • • • Obtenga el autómata M que originó la gramática G Obtenga una gramática limpia a partir de G sin reglas nulas ni unitarias Sea el homomorfismo {h(a)=bc ,h(b)=ab, h(c)=a} Indique mediante una expresión regular simplificada el lenguaje H-1(L(M))

SOLUCIÓN

b, Z0/Z0 a, Z0/AZ0 a,A/λ b,A/A

c,Z0/λ

p
La gramática limpia sin reglas nulas ni unitarias sería1: S → a[pAp][pZ0q] | b[pZ0q] | c [pZ0q] → a[pAp][pZ0q] | b[pZ0q] | c [pAp] → b[pAp] | a

q

El lenguaje L(M)= (b + ab*a)*c (cadenas sobre {a,b,c} acabadas en c y...