Download ejer2 PDF

Titleejer2
TagsTheory Of Computation Linguistics Models Of Computation Formal Methods
File Size116.1 KB
Total Pages12
Document Text Contents
Page 6

EJERCICIOS de MAC 1 – ALF (Tema 2) Curso 2010/2011

pág. 6

Sobre ERs (expresiones regulares):

15. Di si son verdad o no las siguientes afirmaciones:

a ) baa ∈ L(a*b*a*b*) b ) L(b*a*) ∩ L( a*b*) = L(a* ∪ b*)
c ) L(a*b*) ∩ L(c*d*) = ∅ d ) abcd ∈ L((a(cd)*b)*)
e) Las expresiones regulares α = εεεε y β=(εεεε∪∪∪∪∅∅∅∅)* son equivalentes.


16. Para las siguientes expresiones regulares, escribe todas las palabras de longitud

menor o igual que seis pertenecientes al lenguaje que generan, y describe dicho

lenguaje en cada caso:

a ) (10)* ∪ (01)* b ) (10 ∪ 01)*
c ) (11 ∪ 0)*(00 ∪ 1)* d ) (1 ∪ 01 ∪ 001)*(ε ∪ 0 ∪ 00)
e ) [00 ∪ 11 ∪ (01 ∪ 10)(00 ∪ 11)*(01 ∪ 10)]*


17. Sea Σ ={a,b}. Escribe expresiones regulares para los siguientes lenguajes:

a ) cadenas con al menos tres a's

b ) cadenas con a lo sumo tres a's

c ) cadenas con un número de a's divisible por 3

d ) cadenas con al menos una aparición de la subcadena aaa

e) cadenas en las que las a's van agrupadas como mínimo de tres en tres.



18. Sea Σ ={a,b}. Construye una expresión regular para el lenguaje formado por las
cadenas que no contienen la subcadena aaa. Se debe hacer primero el AFD,

obtener a partir de él la GRD y, resolviendo las ecuaciones correspondientes,

llegar a la expresión regular.

19. (Ejercicio especial) Sea Σ ={a,b}. Construye una expresión regular para el
lenguaje formado por las cadenas que contienen exactamente una aparición de

la subcadena aaa. Se debe hacer primero el AFD, obtener a partir de él la GRD

y, resolviendo las ecuaciones correspondientes, llegar a la expresión regular.

Page 12

EJERCICIOS de MAC 1 – ALF (Tema 2) Curso 2010/2011

pág. 12

35. Di si son ciertas o falsas las siguientes afirmaciones, razonando tu respuesta de

forma breve pero convincente.

a) Tenemos un AFD sobre el alfabeto {a,b} que contiene dos estados no

finales, p y q, con las siguientes transiciones:

a b

p p q

q p q

Sin conocer el resto del autómata podemos asegurar que estos estados son

necesariamente indistinguibles.

b) Si M = (Q, Σ, δ, q0, F) es el autómata mínimo equivalente al AFD, N = (P,
Σ, γ, p0, G), el cardinal de F y G ha de ser el mismo.



36. Demuestra que no son regulares sobre el alfabeto Σ = { a , b } :

a ) { w w ∈Σ*: w es la palabra que resulta de cambiar cada aparición en w de a
por b y viceversa }

b ) { w ∈Σ*: w = wR ∧ |w|a = |w|b }
c ) { anbm: m ≤ n ≤ 2*m }

d ) { aibjak: j = max(i,k) }

e ) { aibjak : i, j, k >0 ∧ (i ≤ j ∨ j ≥ k ∨ i = k) }
f ) { aibjak : i, j, k >0 ∧ (i = j ∨ i = k ∨ j = k) }
g ) { w ∈Σ* : w tiene al menos un prefijo con más b's que a's }


37. Considera el alfabeto { M, D, C, L, X, V, I } y el lenguaje de los números

romanos. Demuestra que es un lenguaje regular construyendo un autómata

finito con transiciones vacías que lo reconozca. Recuerda que, por ejemplo, VIIII

no es un número romano, y que debemos escribir IX, en su lugar. Puede

resultarte útil construir la expresión regular y luego el ε-AFND
correspondiente.

Similer Documents