Lenin Torres Prueba de Ensayo Primer Bimestre Teoría de Autómatas y Lenguajes Formales

Teoría de Autómatas y Lenguajes Formales

Prueba de Ensayo Primer Bimestre

Lenin Torres

1 Ejercicios de Expresiones regulares.

1.1 Todas las cadenas de a y b que no contengas tres b consecutivas

∑={a,b}

L={a,aa,b,bb,ab,aba,ba,bab,..}

a*+b+bb+a*b+a*bb+(ab)*a+(ab)*a*b+(ab)*a*bb+(ba)*a*b+(ba)*a*bb

1.2 Todas las cadenas de letras minúsculas que comiencen y terminen con dos a.

∑={a,b}

L={aaaa,aabaa,aaabaa,aabaaa}

aa+[a..z]+aa

1.3 Cadenas de dígitos que representen números impares

∑={0,1,2,3,4,5,6,7,8,9}

L={1,3,4,13,19}

[0...9]*+(1+3+5+7+9)

1.4 Expresiones que satisfagan la condición dada para el alfabeto {0,1}

1.4.1 Número par de a en la cadena w

No se puede describir con expresión regular puesto que no tiene memoria para contar el número de apariciones

1.4.2 Que no tenga la cadena abc en la cadena w

a*+b*+(a*b*c*)+(b*c*a*)

2 Describir los AFD que acepten los lenguajes siguientes del alfabeto {0,1}

2.1 Conjunto de todas las cadenas con dos ceros consecutivos (no necesariamente al final)

2.2 Conjunto de cadenas que contengan subcadena 011

1 De 9

Lenin Torres Prueba de Ensayo Primer Bimestre Teoría de Autómatas y Lenguajes Formales

2.3 Conjunto de palabras de {a,b}, que no contengan aaa

3 Convertir los AFN del ejercicio 2.4.1 en AFD

3.1 AFN que reconoce abc, abd y aacd del alfabeto {a,b,c,d}

3.1.1 Diagrama del AFN

3.1.2 Tabla para calcular los subconjuntos

Nombres EstadosSímbolos

a b c d

A q0 B={q0,q1,q4,q7} {q0} {q0} {q0}

B {q0,q1,q4,q7} C={q0,q1,q4,q7,q8} D={q0,q2,q5} {q0} {q0}

C {q0,q1,q4,q7,q8} {q0,q1,q4,q7,q8} {q0,q2,q5} E={q0,q9} {q0}

D {q0,q2,q5} {q0,q1,q4,q7} {q0} F={q0.q3} G={q0,q6}

E {q0,q9} {q0,q1,q4,q7} {q0} {q0} H={q0,q10}

F {q0,q3} {q0,q1,q4,q7} {q0} {q0} {q0}

G {q0,q6} {q0,q1,q4,q7} {q0} {q0} {q0}

H {q0,q10} {q0,q1,q4,q7} {q0} {q0} {q0}

2 De 9

Lenin Torres Prueba de Ensayo Primer Bimestre Teoría de Autómatas y Lenguajes Formales

3.1.3 Tabla de transiciones del AFD resultante

Símbolos

Estados a b c d

→ A B A A A

B C D A A

C C D E A

D B A F G

E B A A H

* F B A A A

* G B A A A

* H B A A A

3.2 AFN que reconoce 0101, 101, 011 alfabeto {0,1}

3.2.1 Diagrama del AFN

3.2.2 Tabla para calcular los subconjuntos

Nombres EstadosSímbolos

0 1

A q0 B={q1,q8} C={q5}

B {q1,q8} {} D={q2,q9}

C {q5} E={q6} {}

D {q2,q9} F={q3} G={q10}

3 De 9

Lenin Torres Prueba de Ensayo Primer Bimestre Teoría de Autómatas y Lenguajes Formales

E {q6} {} H={q7}

F {q3} {} I={q4}

G {q10} {} {}

H {q7} {} {}

I {q4} {} {}

J {} {} {}

3.2.3 Tabla de transiciones del AFD resultante

EstadosSímbolos

0 1

A B C

B J D

C E J

D F G

E J H

F J I

G J J

H J J

J J J

3.3 AFN que reconoce ab, bc y ca del alfabeto {a,b,c}

3.3.1 Diagrama del AFN

4 De 9

Lenin Torres Prueba de Ensayo Primer Bimestre Teoría de Autómatas y Lenguajes Formales

3.3.2 Tabla para calcular los subconjuntos

Nombres EstadosSímbolos

a b c

A {q0} B={q1} C={q0,q3} D={q0,q5}

B {q1} {} E={q2} {}

C {q0,q3} {q1} {q0,q3} F={q0,q5,q4}

D {q0,q5} G={q1,q6} {q0,q3} {q0,q5}

E {q2} {} {} {}

F {q0,q5,q4} {q1,q6} {q0,q3} {q0,q5}

G {q1,q6} {} {q2} {}

H {} {} {} {}

3.3.3 Tabla de transiciones del AFD resultante

Símbolos

Estados a b c

→ A B C D

B H E H

C B C F

D G C D

* E H H H

* F G C D

* G H E H

H H H H

4 Realizar lo solicitado para el AFD descrito por la tabla de transiciones:

0 1

→ q1 q2 q1

q2 q3 q1

* q3 q3 q2

5 De 9

Lenin Torres Prueba de Ensayo Primer Bimestre Teoría de Autómatas y Lenguajes Formales

Para facilitar la solución se usa el gráfico del AFD

4.1 Obtener todas las expresiones regulares R 0ij

R 011

ε+1

R 012

0

R 013

θ

R 021

1

R 022

ε

R 023

0

R 031

θ

R 032

1

R 033

ε+0

4.2 Obtener todas las expresiones regulares R 1ij

. Esto se calcula con:

6 De 9

Lenin Torres Prueba de Ensayo Primer Bimestre Teoría de Autómatas y Lenguajes Formales

R 1ij=R0

ijR0

i1R0

11∗R0

ij

Sustitución Simplificado

R 111

ε+1+(ε+1)[(ε+1)]*(ε+1) 1*

R 112

0+(ε+1)[(ε+1)]*0=0+11*0=1*0 1*0

R 113

θ+(ε+1)[(ε+1)]*θ=11∗θ θ

R 121

1+1(ε+1)*1=1+11*1 11*

R 122

ε+1[(ε+1)]*ε ε+11*0

R 123

0+1[(ε+1)]*0=0+1*0 0

R 131

θ+θ[(ε+1)]∗ θ θ

R 132

1+θ[(ε+1)]∗1=1+1∗1=1+1 1

R 133

(ε+0)+θ[(ε+0)]∗(ε+0)= ε+0

7 De 9

Lenin Torres Prueba de Ensayo Primer Bimestre Teoría de Autómatas y Lenguajes Formales

4.3 Obtener todas las expresiones regulares R 2 ij

La expresión en este caso es R 2 ij=R 1

ijR 1

i2R 1

22∗R1

2j

Sustitución Simplificado

R 2 11

(1*)+(1*0)[(ε+11*0)]*11*=1*+(1*0)[11*0]*1* 1*+(1*0)[11*0]*1*

R 2 12

1*0+(1*0)[(ε+11*0)]*(ε+11*0) = 1*0+(11*0)*11*0

1*0+(11*0)*11*0

R 2 13

θ+(1∗0)[(ε+11*0)]∗0=1∗0[(11∗0)]∗0 1∗0[(11∗0)]∗0

R 2 21

(11*)+(ε+11*0)[(ε+11*0)]*11*=(11*)+(11*0)(11*0)*11*

(11*)+(11*0)*11*

R 2 22

(ε+11*0)+(ε+11*0)(ε+11*0)*(ε+11*0) 11*0

R 2 23

0+(ε+11*0)(ε+11*0)*0=0+(11*0)(11*0)*0 0+(11*0)*0

R 2 31

θ+1[(ε+11*0)]∗11∗=1(11∗0)∗11∗ 1(11∗0)∗11∗

R 2 32

1+1[(ε+11*0)]∗(ε+11*0)=1+1(11*0)*(11*0) 1+1(11*0)*(11*0)

R 2 33

(ε+0)+1[(ε+0)]*0=0+10*0 0+10*0

4.4 Obtener la expresión regular para el AFD

4.5 Construir el Diagrama de Transiciones del AFD y obtener una expresión regular eliminando el estado q2

8 De 9

Lenin Torres Prueba de Ensayo Primer Bimestre Teoría de Autómatas y Lenguajes Formales

La expresión regular para este último es (1+01+00(0+10)*11)*00(0+10)*

9 De 9