Ejercicios teoria de automatas y lenguajes formales

Febrero 2003

1.a)

La={aibj | i es par, i>j}

w= xyz = a2nbm , 2n>m

Utilizamos la inversa de la palabra

w´= xykz , ∀ k≥0 . |xy|≤n , y≠ℰ

wR=bna2n , x=ℰ , y = bn , z= a2n ,

Para k=2 ( xy2z = b2na2n

Llegamos a la contradicción 2n=m.

No cumple el Lema de Bombeo.

La no es un lenguaje regular.

2.

ℰ - AFN

[pic]

AFN

[pic]

1.b).

Lb= { w Є{0,1}* | w = wR}

w= xyz = anXan

y ≠ ℰ , |xy| ≤ n,

w´= xykz = arasan-r-sXan

Con k=0 ( w´= xykz = an-sXan

Llegamos a la contradicción n-s≠n

No cumple el lema de bombeo.

Lb no es un lenguaje regular.

AFD

[pic]

3.a)

X0(0X1+1X3

X1(0X2+1X0+ℰ

X2(0X3+1X3

X3(0X3+1X3

Eliminamos los estados trampa (X3) y las transiciones que lleven a ellos

X0(0X1X1(1X0+ℰ

Sustituimos hasta llegar a la ER

X0(0(1X0+ℰ)

X0(0(10)*

3.b)

[pic]

5.a) X0(1X0+0X1 Sustituimos de abajo a arriba

X1(0X2+0X3 X2(1X2+1 (1*1

X2(1X2+1X3 X1(01*1+0

X3(ℰ X0(1X0+0(01*1+0)(1*0(01*1+0)

Simplificando E.R. = 1*(00)1*

Febrero 2004

1. L= {wRwwR | w Є {a,b}}

|xy|≤n , y ≠ ε

w=xyz=XnXnXn (X es una colección de a`s yb`s cuyo orden es indiferente, pues solo vamos a utilizar el número de elementos)

x=Xr y=Xs z=Xn-r-sXnXn
W´=xykz. Para k=0(Xr(Xs)0Xn-r-sXnXn
W´=Xn-sXnXn
Llegamos a la contradicción |wR|=n-s ≠|w|=n.
No cumple el lema de bombeo.
El lenguaje no es regular.

2.a)[pic]

2.b)

[pic]

3.1.

[pic]

3.2.

X0(aX1+bX3
X1(aX0+bX2
X2(aX3+bX1
X3(aX2+bX0+ε
E.R.=((aa+ab(bb)*ba)*(b+ab(bb)*a)(a(bb)*a)*(b+a(bb)*ba))*(aa+ab(bb)*ba)*(b+ab(bb)*a)(a(bb)*a)*

4.1.

[pic]

4.2.

[pic]

4.3.

S(0A|1B
A(0C|1B
B(0A|1D
C(0E|1B
D(0A|1F
E(0E|1G|ε
F(0H|1F|ε
G(0H|1F|ε
H(0E|1G|ε

Febrero 2005

1.L= {wϵ{a,b}* | w=z1azaz2 siendo z,z1,z2 ϵ {a,b}* y |z|=4i (múltiplo de 4) para algún i ≥ 0}

[pic]

Falta AFD, duda para tutorías.

2.a)
L= {aibja2i | i,j ϵN, i,j > 0}
w=xyz=anbma2n
|xy|≤n y≠ε
x=ar y=as z=an-r-sbma2n
w´=xykz= Para k=0( ar(as)0an-r-sbna2n
w´=an-sbna2n
Llegamos a la contradicción 2n ≠ 2*(n-s).
La segunda parte de a`s tiene más deldoble de a`s que tiene la primera parte
No cumple el lema de bombeo.
El lenguaje no es regular.
2.b)
L= {0i1j0j+1 | i,j ЄN, i,j > 0}
w=xyz=0m1n0n+1
Utilizamos la palabra inversa wR
wR=0n+11n0m
|xy|≤n y≠ε
x=0r y=0s z=0n-r-s+11n0m
w´=xykz. Para k=0(0r(0s)00n-r-s+11n0m
w´=0n-s+11n0m
Llegamos a la contradicción n-s+1≠n+1, puesto que s≠0.
Nocumple el lema de bombeo.
El lenguaje no es regular.

3.a)

ER: (((00)* + (00)*0)10 + ((11)* + (11)*1)10)*

Simplificamos la expresión:

((00)*+(00)*0) nos genera todos los ceros(pares e impares)(0*

((11)*+(11)*1) nos genera todos los unos(pares e impares)(1*

Sustituimos((0*10)*+(1*10)*

Sacamos factor común (((0*+1*)10)*

AFD

[pic]

3.b)

S(0A|1B|ℰA(0A|1C

B(0S|1B

C(1D|0S

D(0D|1D

Febrero 2006

1.

L={ai/2bjci | i es par, i,j>0}

Utilizamos la palabra inversa
wR=xyz=cnbman/2
|xy|≤n y≠
x=cr y=cs z=cn-r-sbman/2
w´=xykz=(para k=0)= cr(cs)0cn-r-sbman/2
w´=cn-sbman/2
Llegamos a la contradicción n≠n-s, puesto que s≠0.
|cn-s|j}

w=xyz=0n1m22n
|xy|≤n y≠ε
x=0r y=0s z=0n-r-s1m22nw´=xykz. Para k=0(0r(0s)00n-r-s1m22n
w´=0n-s1m22n
Llegamos a la contradicción 2*(n-s)≠2*n , puesto que s≠0.
El número de 0`s no es la mitad que el número de 2`s.
No cumple el Lema de bombeo
El lenguaje no es regular. No se puede construir un AF.

2.f)

Utilizo el modulo 5 para hacer los estados

Como 0 no es múltiplo de 5, necesitamos un estado inicial diferenciado....