matematicas para la computacion jose jimenez murillo slideshare2

325 Respuestas, introducción a los lenguajes formales

9.- Introducción a los lenguajes formales:

9.1.-

a) Es regular. Ya que únicamente tienen un símbolo no terminal del lado izquierdo de todas

las composiciones y del lado derecho tiene a lo más un solo símbolo no terminal.

También es libre de contexto y sensible al contexto.

b) No es regular. Ya que tiene más de un símbolo no terminal del lado izquierdo de algunas

composiciones.

No es libre de contexto. Ya que del lado izquierdo de algunas composiciones hay más de

un símbolo no terminal, además algunas composiciones tienen mayor número de símbolos

del lado izquierdo que del lado derecho.

Es sensible al contexto. Ya que no guarda ninguna restricción.

c) No es regular. Ya que algunas composiciones tienen del lado derecho más de un símbolo

no terminal.

Es libre de contexto. Ya que del lado izquierdo de la composición tienen un solo símbolo

no terminal.

Es sensible al contexto ya que toda gramática libre de contexto es también sensible al

contexto.

9.2.-

a) No es regular. Ya que tiene más de un símbolo no terminal del lado izquierdo de algunas

composiciones. Además de que del lado derecho, algunas de las composiciones tienen

más de un símbolo no terminal.

No es libre de contexto. Ya que del lado izquierdo de algunas composiciones hay más de

un símbolo no terminal, además algunas composiciones tienen mayor número de símbolos

del lado izquierdo que del lado derecho.

Es sensible al contexto. Ya que no guarda ninguna restricción.

b) No es regular. Ya que algunas composiciones tienen del lado derecho más de un símbolo

no terminal.

Es libre de contexto. Ya que del lado izquierdo de la composición tienen un solo símbolo

no terminal.

Es sensible al contexto ya que toda gramática libre de contexto es también sensible al

contexto.

c) Es regular. Ya que únicamente tienen un símbolo no terminal del lado izquierdo de todas

las composiciones y del lado derecho tiene a lo más un solo símbolo no terminal.

También es libre de contexto y sensible al contexto.

326 Respuestas, introducción a los lenguajes formales

9.3.-

a)

szBzyCzyxCzyxzAzyxzzBzyxzzzszyxzzzz

Representación con notación BNF.

s::= xs / zB / yA / z

A::= xA / yC / zB / y

B::= yC / xA / zs

C::= zA / xC / yB / y

b)

syAyxBAyxBxAyxAzByCBByCAyyByCyzyyByzzzyyxx

Representación con notación BNF.

s::= yA

A::= xBA / yz

B::= Ayy / Bx / xx

Cy::= zz

xAz::=CB

BxA::=AzB

c)

sxBxyyCxyyBxAxyyyyyCxAxyyyyxyxAxyyyyxyxCBxxyyyyxyxxyxx

Árbol de derivación.

s

z B

y C

x C

z A

z B

z s

z

Respuestas, introducción a los lenguajes formales 327

Representación con notación BNF.

s::= xB

A::= xBy / CBx / y

B::= yxC / yyC / x

C::= BxA / xy

Representación con diagrama sintáctico.

y

s

x B

y C y

x B A

y y C

x y

C B x

x x

B

C

x

x

y

A

y

B

s x B

C y

y

x

B

x

C y

328 Respuestas, introducción a los lenguajes formales

9.4.-

a)

La palabra zyyyzx no pertenece a este lenguaje, por lo tanto no se puede derivar.

La derivación de la palabra zyyyxxyyzx es como sigue:

sBxA DyAA DyzBC CDBCCxACC CxAyyzx Cxxyyzx zyByyzx

zyyCxyyzx zyyyxxyyzx

Representación de la gramática usando BNF.

s::= BxA Bx::= DyA Cxx::= zyB

B::= yCx BA::= yzz

C::= BA / yx Dyz::= CD

AA::= zBC DB::= xAC

Ay::= xy CC::= yyzx

b)

La derivación de la palabra yxxxxyxxyyy es como sigue:

s yA yxAB yxxCB yxxxB yxxxxBy yxxxxAyyy yxxxxBxxyyy

yxxxxyxxyyy

Árbol de derivación.

C

B

y x

x A

A

x

s

y A

x B A

x C

x

B y

y y

B x x

y

Respuestas, introducción a los lenguajes formales 329

Representación de la gramática usando BNF.

s::= yA

A::= xC / xAB / Bxx / yx

B::= xBy / Ayy / yC / y

C::= x

Representación con diagrama sintáctico.

s x A

C x

x

x

B A

B x

y x

A

B x

y A

C y

y

B

y

y

C x

330 Respuestas, introducción a los lenguajes formales

c)

La derivación de la palabra 010011 es como sigue:

s 0A1 010A1 010011

La derivación de la palabra 11110000 es:

s1A0 11A00 111A000 11110000

La palabra 01011010 no pertenece a este lenguaje, por lo tanto no se puede derivar.

Árboles de derivación para las palabras 0110011 y 11110000.

Representación de la gramática usando BNF.

s::= 0A1 / 1A0

A::= 0A1 / 1A0 / 10A / 01A / 01 / 10

Representación con diagrama sintáctico.

s

0 1 A

1 0 A

0 1

010011

s

1 0 A

1 A 0

1 0

11110000

1 A 0

s

A

0 1

0

A

1

Respuestas, introducción a los lenguajes formales 331

9.5.-

a) (LM) = { ε, 0, 1, 00, 01, 10, 000, 100, 111}.

b) (LM) = {00, 111}

c) LM = {01, 000, 001, 0100, 0111, 0000, 11, 100, 101, 1100, 1111, 1000, 0001, 00100,

00111, 00000, 1001, 10100, 10111, 10000, 11100, 11101, 111100, 11111, 111000}

d) L-M = { ε, 0, 10}

e) MI = {1, 00, 10, 001, 111, 000}

f) LI

= { ε ,0, 1, 00, 01, 111}

g) L2 = LLL

0=LL{ε}= LL = {00, 01, 000, 010, 0111, 10, 11, 100, 110, 1111, 001, 0000,

0010, 00111, 101, 1000, 1010, 10111, 1110, 11100, 11110, 111111}

h) L+ = L

1 L

2 L

3 …… L

∞ = {0, 1, 00, 10, 111}{00, 01, 000, 010, 0111, 10, 11,

100, 110, 1111, …………. }….. = {0, 1, 00, 10, 111, 01, 000, 010, 0111, 11, 100,

110, 1111, …………., 111111, ………}

i) L*= L0 L

1 L

2 …… L

∞ = { ε}{0, 1, 00, 10, 111}{00, 01, 000, 010, 0111, 10,

11, 100, 110, 1111, …………. }……= { ε, 0, 1, 00, 10, 111, 01, 000, 010, 0111, 11,

100, 110, 1111, …………., 111111, ………}

j) Lc =L’= L*- L = {x / x es una cadena de 0s y 1s; xL*; xL}

9.6.-

L= {0, 11, 100}; M={0, 10, 11, 100, 101}

A 1

1 A

1

A

0

0

0

1

A 0 1

0 A 1

0 1

1

332 Respuestas, introducción a los lenguajes formales

a) LI ={0, 11, 001}

b) MI ={0, 01, 11, 001, 101}

c) L+= L

1 L

2 L

3 …… L

∞ = {0, 11, 100}{00, 011, 0100, 110, 1111, 11100, 1000,

10011, 100100} {000, 0011, 00100, 0110, 01111, 011100, 01000, 010011, 0100100,

1100, 11011, 110100, 11110, 111111, 1111100, 111000, 1110011, 11100100, 10000,

100011, 1000100, 100110, 1001111, 10011100, 1001000, 10010011, 100100100}…..

={0, 11, 100, 00, 011, 0100, 110, 1111, 11100, 1000, 10011, 100100, 000, 0011, 00100,

0110, 01111, 011100, 01000, 010011, 0100100, 1100, 11011, 110100, 11110, 111111,

1111100, 111000, 1110011, 11100100, 10000, 100011, 1000100, 100110, 1001111,

10011100, 1001000, 10010011, 100100100,…………..}

d) M+= M

1 M

2 M

3 …… M

∞ =

{0, 10, 11, 100, 101}{00, 010, 011, 0100, 0101,

100, 1010, 1011, 10100, 10101, 110, 1110, 1111, 11100, 11101, 1000, 10010, 10011,

100100, 100101, 1010, 10110, 10111, 101100, 101101} ={000, 0010, 0011, 00100,

00101, 0100, 01010, 01011, 010100, 010101, 0110, 01110, 01111, 011100, 011101,

01000, 010010, 010011, 0100100, 0100101,…….}

e) MI

={0, 01, 11, 001, 101}

f) L 2= LLL

0 = LL{ε}= LL = {00, 011, 0100, 110, 1111, 11100, 1000, 10011, 100100}

g) M3= MMMM

0 = MMM{ε}= MMMM = {000, 0010, 0011, 00100, 00101, 0100, 01010,

01011, 010100, 010101, 0110, 01110, 01111, 011100, 011101, 01000, 010010, 010011,

0100100, 0100101, 01010, 010110, 010111, 0101100, 0101101, 1000, 10010, 10011,

100100, 100101, 10100, 101010, 101011, 1010100, 1010101, 10110, 101110, 101111,

1011100, 1011101, 101000, 1010010, 1010011, 10100100, 10100101, 101010, 1010110,

1010111, 10101100, 10101101, 1100, 11010, 11011, 110100, 110101, 11100, 111010,

111011, 1110100, 1110101, 11110, 111110, 111111, 1111100, 1111101, 111000,

1110010, 1110011, 11100100, 11100101, 111010, 1110110, 1110111, 11101100,

11101101, 10000, 100010, 100011, 1000100, 1000101, 100100, 1001010, 1001011,

10010100, 10010101, 100110, 1001110, 1001111, 10011100, 10011101, 1001000,

10010010, 10010011, 100100100, 100100101, 1001010, 10010110, 10010111,

100101100, 100101101, 10100, 101010, 101011, 1010100, 1010101, 101100, 1011010,

1011011, 10110100, 10110101, 101110, 1011110, 1011111, 10111100, 10111101,

1011000, 10110010, 10110011, 101100100, 101100101, 1011010, 10110110, 10110111,

101101100, 101101101}

h) (LMI ) = {0, 11, 100}{0, 01, 11, 001, 101}= {0, 01, 11, 001, 100, 101}

i) (M-L) = {0, 10, 11, 100, 101}-{0, 11, 100}= {10, 101}

j) LM = L= {00, 010, 011, 0100, 0101, 110, 1110, 1111, 11100, 11101, 1000, 10010, 10011,

100100, 100101}

k) Mc = M’= M*-M ={x / x es una cadena de 0s y 1s; xM*; xM}

l) (M’ )I ={x / x es una cadena de 0s y 1s; xM’; x está escrita a la inversa}

Respuestas, introducción a los lenguajes formales 333

9.7.-

L={110}

a) L+ = L

1 L

2 L

3 …… L

∞ = {dias}{diasdias}{diasdiasdias}…..= { dias,

diasdias, diasdiasdias,…..}

b) L* = {ε}{L+}= { ε, dias, diasdias, diasdiasdias,…..}

c) LI = {said}

d) (L+)2 = L

+ L

+ = {dias, diasdias, diasdiasdias,….}{ dias, diasdias, diasdiasdias,….} = {

diasdias, diasdiasdias, diasdiasdiasdias,…..}

e) (L+)I = {said, saidsaid, saidsaidsaid,…….}

f) (LI)

+ = (L

I )1 (L

I )2 (L

I )3 …… (L

I )∞

= {said} {saidsaid} {saidsaidsaid}

….. = {said, saidsaid, saidsaidsaid,……}

g) (L*) I = { ε, said, saidsaid, saidsaidsaid,……}

h) (LI )* = {ε}

0 (L

I)

+ = { ε, said, saidsaid, saidsaidsaid,……}

i) Lc =L* - L

= {x / xL*; x≠dias}

j) (Lc)

I = {ε, saidsaid, saidsaidsaid, saidsaidsaidsaid,…… }

k) (L*)c =(L*)’=

l) (L+)c = (L

+)’= {ε}

9.8.-

a) L*{ε}{L+}={ ε, 110, 110110, 110110110, 110110110110, …………}

b) L+= L

1 L

2 L

3 …… L

∞ ={110}{110110}{110110110}…={110, 110110,

110110110, 110110110110, …………}

c) LI={011}

d) L4

= LLLLL0 = LLLL{ε}= LLLL = {110110110110}

e) (LI )3={011011011}

f) (L*)I = { ε, 011, 011011, 011011011, 011011011011,…………}

g) (LI)+ = (L

I)1 (L

I)2 (L

I)3 …… (L

I)∞ ={011, 011011, 011011011, 011011011011,

…………}

h) (L+)*= L*

i) (L+)+

= L+

j) (L*)* = L*

k) (L*)’=

l) (L+)’ = {ε}

9.9.-

a) (LM*)I (M

0 M

+ )

I L

I = (M*)

I L

I

(M*)I L

I (M*

)I L

I = (M*)

I L

I

(M* )I L

I = (M*)

I L

I

b) ((ε M)*((L+)+ LL*))

I =( L

+)I (M*)

I

((M)*(L+ L

+))

I =( L

+)I (M*)

I

(M*L+

)I =( L

+)I (M*)

I

( L+)I (M*)

I =( L

+)I (M*)

I

334 Respuestas, introducción a los lenguajes formales

9.10.-

a) ((* L)*)*((M

+ )0 (M

0 MM*)) = L*M*

((ε L)*)*( ε

(M

0 MM*)) = L*M* Ya que *= ε; (M

+ )0 = ε

((ε L)*)*( ε

( ε

M

+)) = L*M* Ya que M

0 = ε; MM*= M

+

(L*)*( ε M*)) = L*M* Ya que (ε

L)*

= L*; ( ε

M

+)= M*

L*M* = L*M* Ya que (L*)*=L*; (ε M*)

= M*

b) (M+)I (L*)

I (((L

+)+ (L

+)0

) (M*M L0)M)

I = (L*M

+)

I

(M+)I (L*)

I ((L

+ ε

) (M*M L

0)M)

I = (L*M

+)

I Ya que (L

+)+

= L+; (L

+)0

) = ε;

(M+)I (L*)

I ((L

+ ε

) (M

+ ε )M)

I = (L*M

+)

I Ya que M*M

= M

+; L

0 = ε;

(M+)I (L*)

I (L* M*M)

I = (L*M

+)

I Ya que (L

+ ε

)=L*; (M

+ ε ) = M*;

(M+)I (L*)

I (L* M

+)I = (L*M

+)

I Ya que M*M =M

+;

(L*)I (M

+)I (L* M

+)I = (L*M

+)

I Ya que (M

+)I (L*)

I = (L*)

I (M

+)I ;

(L* M+)I (L* M

+)I = (L*M

+)

I Ya que (L*)

I (M

+)I = (L* M

+)I

(L*M+)

I = (L*M

+)

I Ya que (L* M

+)I (L* M

+)I = (L*M

+)

I

9.11.-

a)

(t*t*r) (s*s *)

(t*r) (s*s *) Ya que: t*t*=t*

(t*) (s*s *) Ya que. r =

(t*) (s*s *) Ya que: (t*)= t*

(t*) (s+ *) Ya que : s*s =s

+

(t*) (s+ ε) Ya que : *= ε

t*s* Ya que : (s+ ε)=s*

b)

t *t*rεt*t*

tεt*rεt*t* Ya que: *= ε

tt*rt*t* Ya que : εt*=t*

t+rt*t* Ya que : tt*= t

+

t+rt* Ya que : t*t*=t*

c)

(t* s*)(tr)

(t* )(tr) Ya que : s* =

(t* )(tr) Ya que : (t* ) = t*

t*t t*r Ya que : (t* )(tr)= t*t t*r

tt* t*r Ya que : tt* = t*t

t+ t*r Ya que: tt* = t

+

Respuestas, introducción a los lenguajes formales 335

9.12.-

a) (εr +

) (tr*r t*)* = (rt)*

r* (tr*r t*)* = (rt)* Ya que: (εr +

) = r*

r*(tr*r tε )* = (rt)* Ya que: * = ε

r*(tr*r t )* = (rt)* Ya que: tε = t

r*(t r + t )* = (rt)* Ya que: r*r = r

+

r*t*( r + ε )* = (rt)* Ya que: (t r

+ t )* = t*( r

+ ε )*

r*t*(r* )* = (rt)* Ya que: ( r + ε )* = ( r* )*

(r*r*t* )* = (rt)* Ya que: r*t*(r* )* = ( r*r*t* )*

(r*t* )* = (rt)* Ya que: r*r* = r*

(r t )* = (rt)* Ya que: (r*t*)* = (r t )*

b) (εss*)s*s*tr= s*s+tr

(ε s+

)s*s*tr= s*s+tr Ya que: ss*= s

+

s*s*s*tr= s*s+tr Ya que: (ε s

+ )= s*

s* s ε s*tr= s*s+tr Ya que: * = ε

s* s s*tr= s*s+tr Ya que: s ε = s

s* s+tr= s*s

+tr Ya que: s s*= s

+

c) (r*s)* s* (rs)*t = (rs)*(s* t)

(r*s*)* s* (rs)*t = (rs)*(s* t) Ya que: (r*s)* = (r*s*)*

(r s)* s* (rs)*t = (rs)*(s* t) Ya que: (r*s)* = (r s)*

(r s)* (s* t) = (rs)*(s* t) Ya que: (r s)* s* (rs)*t = (r s)* (s* t)

9.13.-

a)

L3

= LLLL0 = LL

2 {ε} = L L

2 = {ab, baa}{ab, baa}{ab, baa}

= {ab, baa}{ abab, abbaa, baaab, baabaa}

= { ababab, ababbaa, abbaaab, abbaabaa, baaabab, baaabbaa,

baabaaab, baabaabaa}

L3L = {ab, baa, ababab, ababbaa, abbaaab, abbaabaa, baaabab,

baaabbaa, baabaaab, baabaabaa}

b)

(ML){ε}= ({a, ab, bb}{ab, baa}) {ε}= {a, ab, bb, baa}{ε}

= {a, ab, bb, baa}

c)

336 Respuestas, introducción a los lenguajes formales

M2 = MMM

0 = {a, ab, bb}{a, ab, bb}{ε}

= { aa, aab, abb, aba, abab, abbb, bba, bbab, bbbb }

LM2 = {ab, baa}{ aa, aab, abb, aba, abab, abbb, bba, bbab, bbbb }

= {abaa, abaab, ababb, ababa, ababab, ababbb, abbba, abbbab, abbbbb,baaaa, baaaab,

baaabb, baaaba, baaabab, baaabbb, baabba, baabbab,baabbbb}

d)

LM = {ab, baa}{a, ab, bb} = { aba, abab, abbb, baaa, baaab, baabb }

(LM)2 = { aba, abab, abbb, baaa, baaab, baabb }{ aba, abab, abbb,

baaa, baaab, baabb }

= { abaaba, abaabab, abaabbb, ababaaa, ababaaab, ababaabb,

abababa, abababab, abababbb, ababbaaa, ababbaaab,

babbaabb, abbbaba, abbbabab, abbbabbb, abbbbaaa,

abbbbaaab, abbbbaabb, baaaaba, baaaabab, baaaabbb,

baaabaaa, baaabaaab, baaabaabb, baaababa, baaababab,

baaababbb, baaabbaaa, baaabbaaab, baaabbaabb,

baabbaba, baabbabab, baabbabbb, baabbbaaa,

baabbbaaab, baabbbaabb}

9.14.-

Sean los lenguajes L= {0, 00}; M={10, 101} sobre el alfabeto ∑={0, 1}. ¿Cuáles son los elementos

de los siguientes lenguajes regulares?.

a) (LM){ε}2

(LM){ε}2 = (LM){εε}= (LM){ε}= (LM)= {0, 00} {10, 101}= {0, 00, 10, 101}

b) M2L = {10, 101}{10, 101}{0, 00}= {1010, 10101, 10110, 101101 }{0, 00}

= {10100, 101000, 101010, 1010100, 101100, 1011000, 1011010, 10110100}

c) M*= {ε}{M+}={ε} M

1 M

2 M

3 …… M

∞ = {ε}{10, 101}{1010, 10101,

10110, 101101 }……= {ε, 10, 101, 1010, 10101, 10110, 101101, …………………. }

d) (LM)2

= (LM)2

= ({0, 00}{10, 101})2

= ({010, 0101, 0010, 00101 })2 = {010, 0101, 0010,

00101 }{010, 0101, 0010, 00101 }= {010010, 0100101, 0100010, 01000101, 0101010,

01010101, 01010010, 010100101, 0010010, 00100101, 00100010, 001000101, 00101010,

001010101, 001010010, 0010100101}

e) L3L

2 =

L2 = {0, 00}{0, 00} = {00, 000, 000, 0000} = {00, 000, 0000}

L3 = LL

2= LLL

0= {0, 00}{00, 000, 0000}{ε} = {000, 0000, 00000, 0000, 00000, 000000}

= {000, 0000, 00000, 000000}{ε}= {000, 0000, 00000, 000000}

f) M*=

g) M*= M{ε}= M = {10, 101}

Respuestas, introducción a los lenguajes formales 337

9.15.-

a)

Expresión regular = a*b(ab)*

b)

Expresión regular = b*ab*a(ab)*

c)

Expresión regular = aab(ab)*

Diagrama de transición

a,b a

b q1

q0

δ a b

q0 q0 q1

q1 q1 q1

E = {q0, q1}

F = {q1}

s = q0

Tabla de transición

a,b

Diagrama de transición

b b

a q2 q0 q1

a

Tabla de transición

δ a b

q0 q1 q0

q1 q2 q1

q2 q2 q2

E = {q0, q1, q2}

F = {q2}

s = q0

a,b

a b b

a a

a,b

Diagrama de transición

b q3 q0 q1

q4

q2

338 Respuestas, introducción a los lenguajes formales

d)

Expresión regular = ab(ab)*b*a

e)

Expresión regular = (b ab)*

Tabla de transición

δ a b

q0 q1 q4

q1 q2 q4

q2 q4 q3

q3 q3 q3

q4 q4 q4

E = {q0, q1, q2, q3, q4}

F = {q3}

s = q0

b

b

a a b

a,b

b

b a

a

Diagrama de transición

a

q3 q0 q1

q4

q2

q5

Tabla de transición

δ a b

q0 q1 q4

q1 q4 q2

q2 q3 q2

q3 q5 q2

q4 q4 q4

q5 q5 q2

E = {q0, q1, q2, q3, q4, q5}

F = {q3}

s = q0

a, b

b

a

a

Diagrama de transición

b

q0 q1 q2

Respuestas, introducción a los lenguajes formales 339

9.16.-

a)

Expresión regular = 100(10)*

b)

Expresión regular = 0*10*1(0*10*1)*

Tabla de transición

δ a b

q0 q1 q0

q1 q2 q0

q2 q2 q2

E = {q0, q1, q2}

F = {q0}

s = q0

1,0

1 0 1

0 1

1,0

Diagrama de transición

0 q3 q0 q1

q4

q2

Tabla de transición

δ 1 0

q0 q1 q4

q1 q4 q2

q2 q4 q3

q3 q3 q3

q4 q4 q4

E = {q0, q1, q2, q3, q4}

F = {q3}

s = q0

1

0

Diagrama de transición

0 0

1 q2 q0 q1

1

340 Respuestas, introducción a los lenguajes formales

c)

Expresión regular = 01(01)*

d)

Expresión regular = 00*10(0*10)*

Tabla de transición

δ 1 0

q0 q1 q0

q1 q2 q1

q2 q2 q1

E = {q0, q1, q2}

F = {q2}

s = q0

Tabla de transición

δ 1 0

q0 q3 q1

q1 q2 q3

q2 q3 q1

q3 q3 q3

E = {q0, q1, q2, q3}

F = {q2}

s = q0

0,1 1

0

Diagrama de transición

0 1

0 q2 q0 q1

1

q3

Respuestas, introducción a los lenguajes formales 341

e)

Expresión regular = 0 1 (01)* (10)*

0

1,0

1 1

1

1 0

0

Diagrama de transición

0 q3 q0 q1

q4

q2

Tabla de transición

δ 1 0

q0 q4 q1

q1 q2 q1

q2 q4 q3

q3 q2 q3

q4 q4 q4

E = {q0, q1, q2, q3, q4}

F = {q3}

s = q0

1

0

1

0

1

1,0 1

0

1 0

Diagrama de transición

0

q2 q0

q5

q1

q3 q4

342 Respuestas, introducción a los lenguajes formales

9.17.-

a)

E = {q0,q1,q2}

F = {q0}

s = q0

b) Conversión del AFN a un AFD.

P(E)={, {q0}, {q1}, {q2}, {q0,q1}, {q0,q2}, {q1,q2}, {q0,q1,q2}}

Donde:

= δ(, a) =

= δ(, b) =

= δ(, c) =

{q0,q1}= δ({q0,q1}, a) = δ(q0,a} δ(q1,a} = {q1}{q0} = {q0, q1}

{q0,q1}= δ({q0,q1}, b) = δ(q0,b} δ(q1,b} = {q2} = {q2}

{q0,q1}= δ({q0,q1}, c) = δ(q0,c} δ(q1,c} = {q0, q2} = {q0, q2}

{q0,q2}= δ({q0,q2}, a) = δ(q0,a} δ(q2,a} = {q1}{q0,q1,q2} = {q0,q1,q2}

{q0,q2}= δ({q0,q2}, b) = δ(q0,b} δ(q2,b} = {q0} = {q0}

{q0,q2}= δ({q0,q2}, c) = δ(q0,c} δ(q2,c} = {q0}= {q0}

{q1,q2}= δ({q1,q2}, a) = δ(q1,a} δ(q2,a} = {q0}{q0,q1,q2} = {q0,q1,q2}

{q1,q2}= δ({q1,q2}, b) = δ(q1,b} δ(q2,b} = {q2}{q0} = {q0,q2}

{q1,q2}= δ({q1,q2}, c) = δ(q1,c} δ(q2,c} = {q0,q2}{q0} = {q0,q2}

{q0,q1,q2}=δ({q0,q1,q2},a)= δ(q0,a} δ(q1,a} δ(q2,a} = {q1}{q0}{q0,q1,q2}

Estado a b c

{q0} {q1}

{q1} {q0} {q2} {q0,q2}

{q2} {q0,q1,q2} {q0} {q0}

Tabla de transición del AFN

Tabla de transición

δ 1 0

q0 q3 q1

q1 q2 q5

q2 q5 q1

q3 q5 q4

q4 q3 q5

q5 q5 q5

E = {q0, q1, q2, q3, q4, q5}

F = {q1, q2, q3, q4}

s = q0

Respuestas, introducción a los lenguajes formales 343

= {q0,q1,q2}

{q0,q1,q2}= δ({q0,q1,q2}, b) = δ(q0,b} δ(q1,b} δ(q2,b} = {q2}{q0}

= {q0,q2}

{q0,q1,q2}= δ({q0,q1,q2}, c) = δ(q0,c} δ(q1,c} δ(q2,c} = {q0,q2}{q0}

= {q0,q2}

De tal forma que la tabla de transiciones debe integrarse con todos los elementos de P(E),

quedando de la siguiente manera.

Elemento a b c

{q0} {q1}

{q1} {q0} {q2} {q0,q2}

{q2} {q0,q1,q2} {q0} {q0}

{q0,q1} {q0, q1} {q2} {q0, q2}

{q0,q2} {q0,q1,q2} {q0} {q0}

{q1,q2} {q0,q1,q2} {q0,q2} {q0,q2}

{q0,q1,q2} {q0,q1,q2} {q0,q2} {q0,q2}

Haciendo:

{q0}= {e0} {q0,q1}= {e3} {q0,q1,q2}= {e6}

{q1}= {e1} {q0,q2}= {e4}

{q2}= {e2} {q1,q2}= {e5}

Los estados aceptados son aquellos que contienen a q0. La tabla de transiciones es:

Elemento a b c

{e0} {e1}

{e1} {e0} {e2} {e4}

{e2} {e6} {e0} {e0}

{e3} {e3} {e2} {e4}

{e4} {e6} {e0} {e0}

{e5} {e6} {e4} {e4}

{e6} {e6} {e4} {e4}

En donde:

e0 es estado inicial

e0, e3, e4, y e6 son estados de

aceptación

344 Respuestas, introducción a los lenguajes formales

De tal forma que el diagrama de transición queda de la siguiente forma:

Eliminando los estados que no se tocan, se tiene el siguiente AFD equivalente:

c)

E = {, e0, e1, e2, e4, e6}

F = {e0, e4, e6}

s = e0

9.18.-

a)

Tabla de transición:

a, b, c

b, c

b, c

a

a

a a

c

a

a

b

c

b, c

b, c

e1

b, c

a

b

e0

e5

e2

e4 e3

e6

a, b, c

b, c

a

a a

a

c

b, c

b, c

e1

b, c

a

b

e0

e2

e4

e6

Estado a b

{q0} {q1} {q0}

{q1} {q2}

{q2} {q0,q1}

Tabla de transición del AFN

Respuestas, introducción a los lenguajes formales 345

E = {q0, q1, q2}

F = {q0, q2}

s = q0

Conversión del AFN a un AFD.

P(E)={, {q0}, {q1}, {q2}, {q0,q1}, {q0,q2}, {q1,q2}, {q0,q1,q2}}

Donde:

= δ(, a) =

= δ(, b) =

{q0,q1}= δ({q0,q1}, a) = δ(q0,a} δ(q1,a} = {q1} = {q1}

{q0,q1}= δ({q0,q1}, b) = δ(q0,b} δ(q1,b} = {q0}{q2} = {q0, q2}

{q0,q2}= δ({q0,q2}, a) = δ(q0,a} δ(q2,a} = {q1}{q0,q1} = {q0,q1}

{q0,q2}= δ({q0,q2}, b) = δ(q0,b} δ(q2,b} = {q0} = {q0}

{q1,q2}= δ({q1,q2}, a) = δ(q1,a} δ(q2,a} = {q0,q1} = {q0,q1}

{q1,q2}= δ({q1,q2}, b) = δ(q1,b} δ(q2,b} = {q2} = {q2}

{q0,q1,q2}=δ({q0,q1,q2},a)= δ(q0,a} δ(q1,a} δ(q2,a} = {q1}{q0,q1}

= {q0,q1}

{q0,q1,q2}= δ({q0,q1,q2}, b) = δ(q0,b} δ(q1,b} δ(q2,b} = {q0}{q2}

= {q0,q2}

De tal forma que la tabla de transiciones debe integrarse con todos los elementos de P(E),

quedando de la siguiente manera.

Elemento a b

{q0} {q1} {q0}

{q1} {q2}

{q2} {q0,q1}

{q0,q1} {q1} { q0, q2}

{q0,q2} {q0,q1} {q0}

{q1,q2} {q0,q1} {q2}

{q0,q1,q2} {q0,q1} {q0,q2}

346 Respuestas, introducción a los lenguajes formales

Haciendo:

{q0}= {e0} {q0,q1}= {e3} {q0,q1,q2}= {e6}

{q1}= {e1} {q0,q2}= {e4}

{q2}= {e2} {q1,q2}= {e5}

Los estados aceptados son aquellos que contienen a q0 y a q2 La tabla de transiciones es:

De tal forma que el diagrama de transición queda de la siguiente forma:

Eliminando los estados que no se tocan, se tiene el siguiente AFD equivalente:

Elemento a b

{e0} {e1} {e0}

{e1} {e2}

{e2} {e3}

{e3} {e1} {e4}

{e4} {e3} {e0}

{e5} {e3} {e2}

{e6} {e3} {e4}

En donde:

e0 es estado inicial

e0, e2, e3, y e4 son estados de

aceptación

a

a,b

b

a

b

a a

a a

b

b

b

b

e1

a

b

e0 e5

e6

e2

e3

e4

Respuestas, introducción a los lenguajes formales 347

Propiedades de los estados.

E = {, e0, e1, e2, e3, e4}

F = {e0, e2, e3, e4}

s = e0

b)

Tabla de transición:

E = {q0, q1, q2}

F = {q1}

s = q0

Conversión del AFN a un AFD.

P(E)={, {q0}, {q1}, {q2}, {q0,q1}, {q0,q2}, {q1,q2}, {q0,q1,q2}}

Donde:

= δ(, a) =

= δ(, b) =

{q0,q1}= δ({q0,q1}, a) = δ(q0,a} δ(q1,a} = { q1, q2} {q1} = { q1, q2}

{q0,q1}= δ({q0,q1}, b) = δ(q0,b} δ(q1,b} = {q0} = {q0}

{q0,q2}= δ({q0,q2}, a) = δ(q0,a} δ(q2,a} = { q1, q2} = {q1, q2}

a

a,b

a

a a

b

b

b

b

e1

a

b

e0

e2

e3

e4

Estado a b

{q0} { q1, q2}

{q1} {q1} {q0}

{q2} {q1}

Tabla de transición del AFN

348 Respuestas, introducción a los lenguajes formales

{q0,q2}= δ({q0,q2}, b) = δ(q0,b} δ(q2,b} = = {q1}

{q1,q2}= δ({q1,q2}, a) = δ(q1,a} δ(q2,a} = {q1} = {q1}

{q1,q2}= δ({q1,q2}, b) = δ(q1,b} δ(q2,b} = {q0}{q1} = {q0, q1}

{q0,q1,q2}=δ({q0,q1,q2},a)= δ(q0,a} δ(q1,a} δ(q2,a} = {q1, q2}{q1}

= {q1, q2}

{q0,q1,q2}= δ({q0,q1,q2}, b) = δ(q0,b} δ(q1,b} δ(q2,b} = {q0} {q1}

= {q0,q1}

De tal forma que la tabla de transiciones debe integrarse con todos los elementos de P(E),

quedando de la siguiente manera.

Elemento a b

{q0} {q1, q2}

{q1} {q1} {q0}

{q2} {q1}

{q0,q1} {q1, q2} {q0}

{q0,q2} {q1, q2} {q1}

{q1,q2} {q1} {q0, q1}

{q0,q1,q2} {q1, q2} {q0,q1}

Haciendo:

{q0}= {e0} {q0,q1}= {e3} {q0,q1,q2}= {e6}

{q1}= {e1} {q0,q2}= {e4}

{q2}= {e2} {q1,q2}= {e5}

Los estados aceptados son aquellos que contienen a q1. La tabla de transiciones es:

Elemento a b

{e0} {e5}

{e1} {e1} {e0}

{e2} {e1}

{e3} {e5} {e0}

{e4} {e5} {e1}

{e5} {e1} {e3}

{e6} {e5} {e3}

En donde:

e0 es estado inicial

e1, e3, e5 y e6 son estados de

aceptación

Respuestas, introducción a los lenguajes formales 349

De tal forma que el diagrama de transición queda de la siguiente forma:

Eliminando los estados que no se tocan, se tiene el siguiente AFD equivalente:

Propiedades de los estados.

E = {, e0, e1, e3, e5}

F = {e0, e3, e5}

s = e0

c)

Tabla de transición:

a

a,b

b

a

b

a

a a

a

b b

b

b

e1

a

b

e0

e2

e4

e6

e5 e3

a

a,b

b

a a

a

b

b

e1

b

e0

e5 e3

Estado a b

{q0} {q1}

{q1} {q2} {q1}

{q2} {q2} {q2, q3}

{q3} {q1}

Tabla de transición del AFN

350 Respuestas, introducción a los lenguajes formales

E = {q0, q1, q2, q3}

F = {q3}

s = q0

Conversión del AFN a un AFD.

P(E)={, {q0}, {q1}, {q2}, {q3}, {q0,q1}, {q0,q2}, {q0,q3}, {q1,q2}, {q1,q3}, {q2,q3},

{q0,q1,q2}, {q0,q1,q3}, {q0,q2,q3}, {q1,q2,q3}, {q0,q1,q2, q3}}

Donde:

= δ(, a) =

= δ(, b) =

{q0,q1}= δ({q0,q1}, a) = δ(q0,a} δ(q1,a} = { q1} {q2} = {q1, q2}

{q0,q1}= δ({q0,q1}, b) = δ(q0,b} δ(q1,b} = {q1} = {q1}

{q0,q2}= δ({q0,q2}, a) = δ(q0,a} δ(q2,a} = {q1} {q2} = {q1, q2}

{q0,q2}= δ({q0,q2}, b) = δ(q0,b} δ(q2,b} = {q2, q3} = {q2, q3}

{q0,q3}= δ({q0,q3}, a) = δ(q0,a} δ(q3,a} = {q1} = {q1}

{q0,q3}= δ({q0,q3}, b) = δ(q0,b} δ(q3,b} = {q1} = {q1}

{q1,q2}= δ({q1,q2}, a) = δ(q1,a} δ(q2,a} = {q2} {q2} = {q2}

{q1,q2}= δ({q1,q2}, b) = δ(q1,b} δ(q2,b} = {q1}{q2, q3} = {q0, q1, q2}

{q1,q3}= δ({q1,q3}, a) = δ(q1,a} δ(q3,a} = {q2} = {q2}

{q1,q3}= δ({q1,q3}, b) = δ(q1,b} δ(q3,b} = {q1}{q1} = {q1}

{q2,q3}= δ({q2,q3}, a) = δ(q2,a} δ(q3,a} = {q2} = {q2}

{q2,q3}= δ({q2,q3}, b) = δ(q2,b} δ(q3,b} = {q2, q3}{q1} = {q1, q2, q3}

{q0,q1,q2}=δ({q0,q1,q2},a)= δ(q0,a} δ(q1,a} δ(q2,a} = {q1}{q2}{q2}

= {q1, q2}

{q0,q1,q2}= δ({q0,q1,q2}, b) = δ(q0,b} δ(q1,b} δ(q2,b} = {q1} {q2, q3}

= {q1,q2,q3}

{q0,q1,q3}=δ({q0,q1,q3},a)= δ(q0,a} δ(q1,a} δ(q3,a} = {q1}{q2}

= {q1, q2}

{q0,q1,q3}= δ({q0,q1,q3}, b) = δ(q0,b} δ(q1,b} δ(q3,b} = {q1} {q1}

= {q1}

Respuestas, introducción a los lenguajes formales 351

{q0,q2,q3}=δ({q0,q2,q3},a)= δ(q0,a} δ(q2,a} δ(q3,a} = {q1}{q2}

= {q1, q2}

{q0,q2,q3}= δ({q0,q2,q3}, b) = δ(q0,b} δ(q2,b} δ(q3,b} = {q2, q3} {q1}

= {q1, q2, q3}

{q1,q2,q3}=δ({q1,q2,q3},a)= δ(q1,a} δ(q2,a} δ(q3,a} = {q2}{q2}

= {q2}

{q1,q2,q3}= δ({q1,q2,q3}, b) = δ(q1,b} δ(q2,b} δ(q3,b} = {q1} {q2, q3} {q1}

= {q1, q2, q3}

{q0,q1,q2, q3}=δ({q0,q1,q2, q3},a)= δ(q0,a} δ(q1,a} δ(q2,a} δ(q3,a} = {q1}{q2}{q2}

= {q1, q2}

{q0,q1,q2, q3}= δ({q0,q1,q2, q3},b)=δ(q0,b}δ(q1,b}δ(q2,b}δ(q3,b}= {q1} {q2, q3}{q1}

= {q1,q2,q3}

De tal forma que la tabla de transiciones debe integrarse con todos los elementos de P(E),

quedando de la siguiente manera.

Elemento a b

{q0} {q1}

{q1} {q2} {q1}

{q2} {q2} {q2, q3}

{q3} {q1}

{q0,q1} {q1, q2} {q1}

{q0,q2} {q1, q2} {q2, q3}

{q0,q3} {q1} {q1}

{q1,q2} {q2} {q0, q1, q2}

{q1,q3} {q2} {q1}

{q2,q3} {q2} {q1, q2, q3}

{q0,q1,q2} {q1, q2} {q1,q2,q3}

{q0,q1,q3} {q1, q2} {q1}

{q0,q2,q3} {q1, q2} {q1, q2, q3}

{q1,q2,q3} {q2} {q1, q2, q3}

{q0,q1,q2,q3} {q1, q2} {q1,q2,q3}

Haciendo:

{q0}= {e0} {q0,q1}= {e4} {q1,q3}= {e8} {q0,q2,q3}= {e12}

{q1}= {e1} {q0,q2}= {e5} {q2,q3}= {e9} {q1,q2,q3}= {e13}

{q2}= {e2} {q0,q3}= {e6} {q0,q1,q2}= {e10} {q0,q1,q2,q3}= {e14}

352 Respuestas, introducción a los lenguajes formales

{q3}= {e3} {q1,q2}= {e7} {q0,q1,q3}= {e11}

Los estados aceptados son aquellos que contienen a q3. La tabla de transiciones es:

De tal forma que el diagrama de transición queda de la siguiente forma:

Elemento a b

{e0} {e1}

{e1} {e2} {e1}

{e2} {e2} {e9}

{e3} {e1}

{e4} {e7} {e1}

{e5} {e7} {e9}

{e6} {e1} {e1}

{e7} {e2} {e10}

{e8} {e2} {e1}

{e9} {e2} {e13}

{e10} {e7} {e13}

{e11} {e7} {e1}

{e12} {e7} {e13}

{e13} {e2} {e13}

{e14} {e7} {e13}

En donde:

e0 es estado inicial

e3, e6, e8, e9, e11, e12, e13, y e14,

son estados de aceptación

b

a b

a

b a

b

a b a

b

a

b a

a,b

a

a,b

b

a

b

a

a

a

a

b

b

b

b

e0

a

b

e12

e5

e4

e9

e3

e11

e2

e6 e8

e13

e14

e1

e7 e10

Respuestas, introducción a los lenguajes formales 353

Eliminando los estados que no se tocan, se tiene el siguiente AFD equivalente:

Propiedades de los estados.

E = {, e0, e1, e2, e9, e13}

F = {e9, e13}

s = e0

d)

Tabla de transición:

E = {q0, q1, q2, q3}

F = {q3}

s = q0

b

a

b

a

a

a,b

a

a

b

b

e0

b

e9 e2

e13

e1

Estado a b

{q0} {q1} {q0, q2}

{q1} {q0, q3}

{q2} {q1}

{q3} {q2, q3}

Tabla de transición del AFN

354 Respuestas, introducción a los lenguajes formales

Conversión del AFN a un AFD.

P(E)={, {q0}, {q1}, {q2}, {q3}, {q0,q1}, {q0,q2}, {q0,q3}, {q1,q2}, {q1,q3}, {q2,q3},

{q0,q1,q2}, {q0,q1,q3}, {q0,q2,q3}, {q1,q2,q3}, {q0,q1,q2, q3}}

Donde:

= δ(, a) =

= δ(, b) =

{q0,q1}= δ({q0,q1}, a) = δ(q0,a} δ(q1,a} = { q1} {q0, q3} = {q0, q1 ,q3}

{q0,q1}= δ({q0,q1}, b) = δ(q0,b} δ(q1,b} = {q0, q2} = {q0, q2}

{q0,q2}= δ({q0,q2}, a) = δ(q0,a} δ(q2,a} = {q1} = {q1}

{q0,q2}= δ({q0,q2}, b) = δ(q0,b} δ(q2,b} = {q0, q2} {q1} = {q0, q1, q2}

{q0,q3}= δ({q0,q3}, a) = δ(q0,a} δ(q3,a} = {q1} = {q1}

{q0,q3}= δ({q0,q3}, b) = δ(q0,b} δ(q3,b} = {q0, q2} {q2, q3} = {q0, q2, q3}

{q1,q2}= δ({q1,q2}, a) = δ(q1,a} δ(q2,a} = {q0, q3} = {q0, q3}

{q1,q2}= δ({q1,q2}, b) = δ(q1,b} δ(q2,b} = {q1} = {q1}

{q1,q3}= δ({q1,q3}, a) = δ(q1,a} δ(q3,a} = {q0, q3} = {q0, q3}

{q1,q3}= δ({q1,q3}, b) = δ(q1,b} δ(q3,b} = {q2, q3} = {q2, q3}

{q2,q3}= δ({q2,q3}, a) = δ(q2,a} δ(q3,a} = =

{q2,q3}= δ({q2,q3}, b) = δ(q2,b} δ(q3,b} = {q1}{q2, q3} = {q1, q2, q3}

{q0,q1,q2}=δ({q0,q1,q2},a)= δ(q0,a} δ(q1,a} δ(q2,a} = {q1}{q0, q3}

= {q0, q1, q3}

{q0,q1,q2}= δ({q0,q1,q2}, b) = δ(q0,b} δ(q1,b} δ(q2,b} = {q0, q2} {q1}

= {q0, q1, q2}

{q0,q1,q3}=δ({q0,q1,q3},a)= δ(q0,a} δ(q1,a} δ(q3,a} = {q1}{q0, q3}

= {q0, q1, q3}

{q0,q1,q3}= δ({q0,q1,q3}, b) = δ(q0,b} δ(q1,b} δ(q3,b} = {q0, q2} {q2, q3}

= {q0, q2, q3}

{q0,q2,q3}=δ({q0,q2,q3},a)= δ(q0,a} δ(q2,a} δ(q3,a} = {q1}

= {q1}

{q0,q2,q3}= δ({q0,q2,q3}, b) = δ(q0,b} δ(q2,b} δ(q3,b} = {q0, q2} {q1} {q2, q3}

= {q0, q1, q2, q3}

{q1,q2,q3}=δ({q1,q2,q3},a)= δ(q1,a} δ(q2,a} δ(q3,a} = {q0, q3}

= {q0, q3}

Respuestas, introducción a los lenguajes formales 355

{q1,q2,q3}= δ({q1,q2,q3}, b) = δ(q1,b} δ(q2,b} δ(q3,b} = {q1} {q2, q3}

= {q1, q2, q3}

{q0,q1,q2, q3}=δ({q0,q1,q2, q3},a)= δ(q0,a} δ(q1,a} δ(q2,a} δ(q3,a} = {q1}{q0, q3}

= {q0, q1, q3}

{q0,q1,q2, q3}= δ({q0,q1,q2, q3},b)=δ(q0,b}δ(q1,b}δ(q2,b}δ(q3,b}={q0,q2} {q1}{q2, q3}

= {q0,q1,q2,q3}

De tal forma que la tabla de transiciones debe integrarse con todos los elementos de P(E),

quedando de la siguiente manera.

Elemento a b

{q0} {q1} {q0, q2}

{q1} {q0, q3}

{q2} {q1}

{q3} {q2, q3}

{q0,q1} {q0, q1 ,q3} {q0, q2}

{q0,q2} {q1} {q0, q1, q2}

{q0,q3} {q1} {q0, q2, q3}

{q1,q2} {q0, q3} {q1}

{q1,q3} {q0, q3} {q2, q3}

{q2,q3} {q1, q2, q3}

{q0,q1,q2} {q0, q1, q3} {q0, q1, q2}

{q0,q1,q3} {q0, q1, q3} {q0, q2, q3}

{q0,q2,q3} {q1} {q0, q1, q2, q3}

{q1,q2,q3} {q0, q3} {q1, q2, q3}

{q0,q1,q2,q3} {q0, q1, q3} {q0,q1,q2,q3}

Haciendo:

{q0}= {e0} {q0,q1}= {e4} {q1,q3}= {e8} {q0,q2,q3}= {e12}

{q1}= {e1} {q0,q2}= {e5} {q2,q3}= {e9} {q1,q2,q3}= {e13}

{q2}= {e2} {q0,q3}= {e6} {q0,q1,q2}= {e10} {q0,q1,q2,q3}= {e14}

{q3}= {e3} {q1,q2}= {e7} {q0,q1,q3}= {e11}

Los estados aceptados son aquellos que contienen a q3. La tabla de transiciones es:

356 Respuestas, introducción a los lenguajes formales

De tal forma que el diagrama de transición queda de la siguiente forma:

Elemento a b

{e0} {e1} {e5}

{e1} {e6}

{e2} {e1}

{e3} {e9}

{e4} {e11} {e5}

{e5} {e1} {e10}

{e6} {e1} {e12}

{e7} {e6} {e1}

{e8} {e6} {e9}

{e9} {e13}

{e10} {e11} {e10}

{e11} {e11} {e12}

{e12} {e1} {e14}

{e13} {e6} {e13}

{e14} {e11} {e14}

En donde:

e0 es estado inicial

e3, e6, e8, e9, e11, e12, e13, y e14,

son estados de aceptación

b

a,b

b

a

b

a

b

a

b

a

b

a b

a

b

a

b

a

a

b

a b

a

a

a

a

b

b

b

e0

a

b

e12

e5

e4

e9

e3

e11

e2

e6

e8

e13

e14

e1

e7

e10

Respuestas, introducción a los lenguajes formales 357

Eliminando los estados que no se tocan, se tiene el siguiente AFD equivalente:

Propiedades de los estados.

E = {, e0, e1, e5, e6, e10, e11, e12, e14}

F = {e6, e11, e12, e14}

s = e0

9.19.-

a) E={e0, e1}, A={00, 01, 10 ,11} y B={0, 1}.

b) s=e0.

c) Diagrama de transiciones.

00,0

10,1

11,0

00,1

01,0

11,1

10,0

e1

01,1

e0

a,b

a

b

b

a

a

b

a

b

a

a b

a

a

b

b

e0

e12

e5

e11

e6

e14

e1

e10 b

358 Respuestas, introducción a los lenguajes formales

d) Tabla de transiciones para las funciones de estado siguiente δ y salida σ.

Edo. δ σ

00 01 10 11 00 01 10 11

e0 e0 e1 e0 e0 0 1 1 0

e1 e1 e1 e0 e1 1 0 0 1

e) La resta de 10001011(2) menos 1101101(2).

Agregando ceros a la izquierda para que las cadenas sean iguales y dos ceros adicionales

para que regrese al estado inicial (en caso de no estarlo) las cadenas a restar son:

010001011(2) menos 001101101(2).

δ (e0, 11) = e0 σ(e0, 11) = 0

δ (e0, 10) = e0 σ(e0, 10) = 1

δ (e0, 01) = e1 σ(e0, 01) = 1 Se debe 1

δ (e1, 11) = e1 σ(e1, 11) = 1 Se debe 1

δ (e1, 00) = e1 σ(e1, 00) = 1 Se debe 1

δ (e1, 01) = e1 σ(e1, 01) = 0 Se debe 1

δ (e1, 01) = e1 σ(e1, 01) = 0 Se debe 1

δ (e1, 10) = e0 σ(e1, 10) = 0

δ (e0, 00) = e0 σ(e0, 00) = 0

De tal forma que el resultado de restar 10001011(2) menos 1101101(2) es 00011110(2)

9.20.-

a)

Elementos de los conjuntos E, A y B

E={e0, e1},

A={00, 01, 02, 03, 04, 05, 06, 07, 10, 11, 12, 13, 14, 15, 16, 17, 20, 21, 22, 23, 24, 25, 26, 27,

30, 31, 32, 33, 34, 35, 36, 37, 40, 41, 42, 43, 44, 45, 46, 47, 50, 51, 52, 53, 54, 55, 56, 57, 60, 61,

62, 63, 64, 65, 66, 67, 70, 71, 72, 73, 74, 75, 76, 77} y

B={0, 1, 2, 3, 4, 5, 6, 7}.

Estado inicial.

s=e0.

Respuestas, introducción a los lenguajes formales 359

Diagrama de transiciones.

Tabla de transiciones para las funciones de estado siguiente δ y salida σ.

δ σ δ σ

e0 e1 e0 e1 e0 e1 e0 e1

00 e0 e0 0 1 40 e0 e0 4 5

01 e0 e0 1 2 41 e0 e0 5 6

02 e0 e0 2 3 42 e0 e0 6 7

03 e0 e0 3 4 43 e0 e1 7 0

04 e0 e0 4 5 44 e1 e1 0 1

05 e0 e0 5 6 45 e1 e1 1 2

06 e0 e0 6 7 46 e1 e1 2 3

07 e0 e1 7 0 47 e1 e1 3 4

10 e0 e0 1 2 50 e0 e0 5 6

11 e0 e0 2 3 51 e0 e0 6 7

12 e0 e0 3 4 52 e0 e1 7 0

13 e0 e0 4 5 53 e1 e1 0 1

14 e0 e0 5 6 54 e1 e1 1 2

15 e0 e0 6 7 55 e1 e1 2 3

16 e0 e1 7 0 56 e1 e1 3 4

17 e1 e1 0 1 57 e1 e1 4 5

20 e0 e0 2 3 60 e0 e0 6 7

21 e0 e0 3 4 61 e0 e1 7 0

22 e0 e0 4 5 62 e1 e1 0 1

e1 e0

00,0 06,6 14,5 23,5 33,6 50,5 01,1 07,7 15,6 24,6 34,7 51,6

02,2 10,1 16,7 25,7 40,4 52,7

03,3 11,2 20,2 30,3 41,5 60,6 04,4 12,3 21,3 31,4 42,6 61,7

05,5 13,4 22,4 32,5 43,7 70,7

17,0 45,1 57,4 71,0 26,0 46,2 62,0 72,1

27,1 47,3 63,1 73,2

35,0 53,0 64,2 74,3 36,1 54,1 65,3 75,4

37,2 55,2 66,4 76,5

44,0 56,3 67,5 77,6

00,1 06,7 15,7 30,4 42,7 01,2 10,2 20,3 31,5 50,6

02,3 11,3 21,4 32,6 51,7

03,4 12,4 22,5 33,7 60,7 04,5 13,5 23,6 40,5

05,6 14,6 24,7 41,6

07,0 37,3 55,3 67,6 16,0 43,0 56,4 70,0

17,1 44,1 57,5 71,1

25,0 45,2 61,0 72,2 26,1 46,3 62,1 73,3

27,2 47,4 63,2 74,4

34,0 52,0 64,3 75,5 35,1 53,1 65,4 76,6

36,2 54,2 66,5 77,7

360 Respuestas, introducción a los lenguajes formales

23 e0 e0 5 6 63 e1 e1 1 2

24 e0 e0 6 7 64 e1 e1 2 3

25 e0 e1 7 0 65 e1 e1 3 4

26 e1 e1 0 1 66 e1 e1 4 5

27 e1 e1 1 2 67 e1 e1 5 6

30 e0 e0 3 4 70 e0 e1 7 0

31 e0 e0 4 5 71 e1 e1 0 1

32 e0 e0 5 6 72 e1 e1 1 2

33 e0 e0 6 7 73 e1 e1 2 3

34 e0 e1 7 0 74 e1 e1 3 4

35 e1 e1 0 1 75 e1 e1 4 5

36 e1 e1 1 2 76 e1 e1 5 6

37 e1 e1 2 3 77 e1 e1 6 7

La suma de 73012(8) mas 26347(8).

Agregando ceros a la izquierda para que las cadenas sean iguales y dos ceros adicionales

para que regrese al estado inicial (en caso de no estarlo) las cadenas a sumar son: 073012(8)

menos 026347(8)..

δ (e0, 27) = e1 σ(e0, 27) = 1

δ (e1, 14) = e0 σ(e1, 14) = 6

δ (e0, 03) = e0 σ(e0, 03) = 3

δ (e0, 36) = e1 σ(e0, 36) = 1

δ (e1, 72) = e1 σ(e1, 72) = 2

δ (e1, 00) = e0 σ(e1, 00) = 1

De tal forma que el resultado de sumar 73012(8) mas 26347(8). Es: 121361(8)

b)

Elementos de los conjuntos E, A y B

E={e0, e1},

A={00, 01, 02, 03, 04, 05, 06, 07, 10, 11, 12, 13, 14, 15, 16, 17, 20, 21, 22, 23, 24, 25, 26, 27,

30, 31, 32, 33, 34, 35, 36, 37, 40, 41, 42, 43, 44, 45, 46, 47, 50, 51, 52, 53, 54, 55, 56, 57, 60, 61,

62, 63, 64, 65, 66, 67, 70, 71, 72, 73, 74, 75, 76, 77} y

B={0, 1, 2, 3, 4, 5, 6, 7}.

Estado inicial.

s=e0.

Respuestas, introducción a los lenguajes formales 361

Diagrama de transiciones.

Tabla de transiciones para las funciones de estado siguiente δ y salida σ.

δ σ δ σ

e0 e1 e0 e1 e0 e1 e0 e1

00 e0 e1 0 7 40 e0 e0 4 3

01 e1 e1 7 6 41 e0 e0 3 2

02 e1 e1 6 5 42 e0 e0 2 1

03 e1 e1 5 4 43 e0 e0 1 0

04 e1 e1 4 3 44 e0 e1 0 7

05 e1 e1 3 2 45 e1 e1 7 6

06 e1 e1 2 1 46 e1 e1 6 5

07 e1 e1 1 0 47 e1 e1 5 4

10 e0 e0 1 0 50 e0 e0 5 4

11 e0 e1 0 7 51 e0 e0 4 3

12 e1 e1 7 6 52 e0 e0 3 2

13 e1 e1 6 5 53 e0 e0 2 1

14 e1 e1 5 4 54 e0 e0 1 0

15 e1 e1 4 3 55 e0 e1 0 7

16 e1 e1 3 2 56 e1 e1 7 6

17 e1 e1 2 1 57 e1 e1 6 5

20 e0 e0 2 1 60 e0 e0 6 5

21 e0 e0 1 0 61 e0 e0 5 4

e1 e0

0,0=0 3,0=3 4,2=2 5,3=2 6,3=3 7,2=5 1,0=1 3,1=2 4,3=1 5,4=1 6,4=2 7,3=4

1,1=0 3,2=1 4,4=0 5,5=0 6,5=1 7,4=3

2,0=2 3,3=0 5,0=5 6,0=6 6,6=0 7,5=2 2,1=1 4,0=4 5,1=4 6,1=5 7,0=7 7,6=1

2,2=0 4,1=3 5,2=3 6,2=4 7,1=6 7,7=0

0,1=7 1,2=7 2,4=6 3,7=4 0,2=6 1,3=6 2,5=5 4,5=7

0,3=5 1,4=5 2,6=4 4,6=6

0,4=4 1,5=4 2,7=3 4,7=5 0,5=3 1,6=3 3,4=7 5,6=7

0,6=2 1,7=2 3,5=6 5,7=6

0,7=1 2,3=7 3,6=5 6,7=7

1,0=0 4,0=3 5,2=2 6,3=2 7,3=3 2,0=1 4,1=2 5,3=1 6,4=1 7,4=2

2,1=0 4,2=1 5,4=0 6,5=0 7,5=1

3,0=2 4,3=0 6,0=5 7,0=6 7,6=0 3,1=1 5,0=4 6,1=4 7,1=5

3,2=0 5,1=3 6,2=3 7,2=4

0,0=7 1,2=6 2,5=4 4,5=6 0,1=6 1,3=5 2,6=3 4,6=5

0,2=5 1,4=4 2,7=2 4,7=4

0,3=4 1,5=3 3,3=7 5,5=7 0,4=3 1,6=2 3,4=6 5,6=6

0,5=2 1,7=1 3,5=5 5,7=5

0,6=1 2,2=7 3,6=4 6,6=7 0,7=0 2,3=6 3,7=3 6,7=6

1,1=7 2,4=5 4,4=7 7,7=7

362 Respuestas, introducción a los lenguajes formales

22 e0 e1 0 7 62 e1 e0 4 3

23 e1 e1 7 6 63 e0 e0 3 2

24 e1 e1 6 5 64 e0 e0 2 1

25 e1 e1 5 4 65 e0 e0 1 0

26 e1 e1 4 3 66 e0 e1 0 7

27 e1 e1 3 2 67 e1 e1 7 6

30 e0 e0 3 2 70 e0 e0 7 6

31 e0 e0 2 1 71 e0 e0 6 5

32 e0 e0 1 0 72 e0 e0 5 4

33 e0 e1 0 7 73 e0 e0 4 3

34 e1 e1 7 6 74 e0 e0 3 2

35 e1 e1 6 5 75 e0 e0 2 1

36 e1 e1 5 4 76 e0 e0 1 0

37 e1 e1 4 3 77 e0 e1 0 7

La resta de 60054(8) menos 7346(8).

Agregando ceros a la izquierda para que las cadenas sean iguales y dos ceros adicionales

para que regrese al estado inicial (en caso de no estarlo) las cadenas a restar son: 060054(8)

menos 007346(8)..

δ (e0, 46) = e1 σ(e0, 46) = 6

δ (e1, 54) = e0 σ(e1, 54) = 0

δ (e0, 03) = e1 σ(e0, 03) = 5

δ (e1, 07) = e1 σ(e1, 07) = 0

δ (e1, 60) = e0 σ(e1, 60) = 5

δ (e0, 00) = e0 σ(e0, 00) = 0

De tal forma que el resultado de 60054(8) menos 7346(8). Es: 050506(8) .

c)

Elementos de los conjuntos E, A y B

E = {e0, e1, e2, e3}

A = {00, 01, 02, 03, 04, 10, 11, 12, 13, 14, 20, 21, 22, 23, 24, 30, 31, 32, 33, 34, 40, 41, 42, 43,

44}

B = {0, 1, 2, 3, 4}.

Estado inicial.

s=e0.

Respuestas, introducción a los lenguajes formales 363

Diagrama de transiciones.

Tabla de transiciones para las funciones de estado siguiente δ y salida σ.

δ σ

e0 e1 e2 e3 e0 e1 e2 e3

00 e0 e0 e0 e0 00 0 1 2 3

01 e0 e0 e0 e0 01 0 1 2 3

02 e0 e0 e0 e0 02 0 1 2 3

03 e0 e0 e0 e0 03 0 1 2 3

04 e0 e0 e0 e0 04 0 1 2 3

10 e0 e0 e0 e0 10 0 1 2 3

11 e0 e0 e0 e0 11 1 2 3 4

12 e0 e0 e0 e1 12 2 3 4 0

13 e0 e0 e1 e1 13 3 4 0 1

14 e0 e1 e1 e1 14 4 0 1 2

20 e0 e0 e0 e0 20 0 1 2 3

21 e0 e0 e0 e1 21 2 3 4 0

22 e0 e1 e1 e1 22 4 0 1 2

23 e1 e1 e1 e1 23 1 2 3 4

2,4=1 3,3=2

4,2=1

0,0=3 1,0=3

0,1=3 1,1=4

0,2=3 2,0=3 0,3=3 3,0=3

0,4=3 4,0=3

4,4=3

1,3=0 2,4=4

1,4=1 3,1=0

2,2=1 3,2=3 2,3=3 4,1=1

3,3=0 4,2=0

3,4=4 4,3=4

4,4=2

4,4=1

3,3=0 3,4=3

4,3=3

1,4=0 2,4=4 4,2=4 2,2=0 3,2=2

2,3=2 4,1=0

0,0=1 1,0=1 2,1=3

0,1=1 1,1=2 3,0=1

0,2=1 1,2=3 3,1=4 0,3=1 1,3=4 4,0=1

0,4=1 2,0=1

0,0=0 1,0=0 2,0=0 4,0=0 0,1=0 1,1=1 2,1=2 4,1=4

0,2=0 1,2=2 2,2=4

0,3=0 1,3=3 3,0=0 0,4=0 1,4=4 3,1=3

2,3=1 2,4=3

3,2=1

3,3=4 4,2=3

e1 e0

e3 e2

3,4=2 4,3=2

0,0=2 0,4=2 2,0=2

0,1=2 1,0=2 2,1=4 0,2=2 1,1=3 3,0=2

0,3=2 1,2=4 4,0=2

1,2=0 2,3=4

1,3=1 3,1=1 1,4=2 3,2=4

2,1=0 4,1=2

2,2=2

3,4=0

4,3=0 4,4=4

364 Respuestas, introducción a los lenguajes formales

24 e1 e1 e1 e2 24 3 4 4 1

30 e0 e0 e0 e0 30 0 1 2 3

31 e0 e0 e1 e1 31 3 4 0 1

32 e1 e1 e1 e1 32 1 2 3 4

33 e1 e2 e2 e2 33 4 0 0 2

34 e2 e2 e2 e3 34 2 3 4 0

40 e0 e0 e0 e0 40 0 1 2 3

41 e0 e1 e1 e1 41 4 0 1 2

42 e1 e1 e2 e2 42 3 4 0 1

43 e2 e2 e2 e3 43 2 3 4 0

44 e3 e3 e3 e3 44 1 2 3 4

La multiplicación de 2304(5) con 32(5).

Multiplicando el dígito de la derecha del multiplicador por el multiplicando ( 2(5) por 02304(5)

) y agregando un cero a la izquierda del multiplicando se tiene:

δ (e0, 24) = e1 σ(e0, 24) = 3

δ (e1, 20) = e0 σ(e1, 20) = 1

δ (e0, 23) = e1 σ(e0, 23) = 1

δ (e1, 22) = e1 σ(e1, 22) = 0

δ (e1, 20) = e0 σ(e1, 20) = 1

Resultado: 10113(5)

Multiplicando el dígito siguiente por el multiplicando ( 3(5) por 02304(5) ) y agregando un

cero a la izquierda del multiplicando se tiene:

δ (e0, 34) = e2 σ(e0, 34) = 2

δ (e2, 30) = e0 σ(e2, 30) = 2

δ (e0, 33) = e1 σ(e0, 33) = 4

δ (e1, 32) = e1 σ(e1, 32) = 2

δ (e1, 30) = e0 σ(e1, 30) = 1

Resultado: 12422(5)

Ahora se deberá usar un autómata para sumar 10113(5) con 12422(5). De tal forma que para este

autómata:

Los elementos de los conjuntos E, A y B

E = {e0, e1},

Respuestas, introducción a los lenguajes formales 365

A = {00, 01, 02, 03, 04, 10, 11, 12, 13, 14, 20, 21, 22, 23, 24, 30, 31, 32, 33, 34, 40, 41, 42, 43,

44} y

B = {0, 1, 2, 3, 4}.

Estado inicial.

s=e0.

Diagrama de transiciones.

Tabla de transiciones para las funciones de estado siguiente δ y salida σ.

δ σ

e0 e1 e0 e1

00 e0 e0 0 1

01 e0 e0 1 2

02 e0 e0 2 3

03 e0 e0 3 4

04 e0 e0 4 0

10 e0 e0 1 2

11 e0 e0 2 3

12 e0 e0 3 4

13 e0 e1 4 0

14 e1 e1 0 1

20 e0 e0 2 3

21 e0 e0 3 4

22 e0 e1 4 0

e1 e0

0,0=0 1,0=1 2,1=3

0,1=1 1,1=2 2,2=4 0,2=2 1,2=3 3,0=3

0,3=3 1,3=4 3,1=4

0,4=4 2,0=2 4,0=4

1,4=0 3,4=2 2,3=0 4,1=0

2,4=1 4,2=1

3,2=0 4,3=2 3,3=1 4,4=3

0,0=1 1,1=3 0,1=2 1,2=4

0,2=3 2,0=3

0,3=4 2,1=4 1,0=2 3,0=4

0,4=0 2,4=2 4,0=0 1,3=0 3,1=0 4,1=1

1,4=1 3,2=1 4,2=2

2,2=0 3,3=2 4,3=3 2,3=1 3,4=3 4,4=4

366 Respuestas, introducción a los lenguajes formales

23 e1 e1 0 1

24 e1 e1 1 2

30 e0 e0 3 4

31 e0 e1 4 0

32 e1 e1 0 1

33 e1 e1 1 2

34 e1 e1 2 3

40 e0 e1 4 0

41 e1 e1 0 1

42 e1 e1 1 2

43 e1 e1 2 3

44 e1 e1 3 4

Agregando un cero a la derecha de la segunda cifra y un cero a la izquierda de la primera (010113(5) ,

124220(5)) se tiene:

δ (e0, 30) = e0 σ(e0, 30) = 3

δ (e0, 12) = e0 σ(e0, 12) = 3

δ (e0, 12) = e0 σ(e0, 12) = 3

δ (e0, 04) = e0 σ(e0, 04) = 4

δ (e0, 12) = e0 σ(e0, 12) = 3

δ (e0, 01) = e0 σ(e0, 01) = 1

De tal forma que el resultado de la multiplicación de: 2304(5) con 32(5).es: 134333(5).

d)

Elementos de los conjuntos E, A y B

E = {e0, e1, e2, e3, e4, e5}

A = {00, 01, 02, 03, 04, 05, 06, 10, 11, 12, 13, 14, 15, 16, 20, 21, 22, 23, 24, 25, 26, 30, 31, 32,

33, 34, 35, 36, 40, 41, 42, 43, 44, 45, 46, 50, 51, 52, 53, 54, 55, 56, 60, 61, 62, 63, 64, 65, 66}

B = {0, 1, 2, 3, 4, 5, 6}.

Estado inicial.

s=e0.

Respuestas, introducción a los lenguajes formales 367

Diagrama de transiciones.

La información que corresponde a cada una de las aristas que salen de los estados e0, e1, e2, e3, e4, y

e5 se muestra en las siguientes tablas.

e0 r00 r01 r02 r03 r04 r05

0,0=0 1,0=0 2,0=0 4,0=4 2,4=1 5,2=3 3,5=1 4,6=3 5,6=2 6,6=1

0,1=0 1,1=1 2,1=2 4,1=1 2,5=3 6,2=5 3,6=4 5,5=4 6,5=2

0,2=0 1,2=2 2,2=4 5,0=5 2,6=5 4,4=2 6,4=3

0,3=0 1,3=3 2,3=6 5,1=5 3,3=2 4,5=6

0,4=0 1,4=4 3,0=0 6,0=0 3,4=5 5,3=1

0,5=0 1,5=5 3,1=3 6,1=6 4,2=1 5,4=6

0,6=0 1,6=6 3,2=6 4,3=5 6,3=4

e1 r10 r11 r12 r13 r14 r15

0,0=1 1,0=1 2,1=3 51=6 1,6=0 3,4=6 3,5=2 4,5=0 5,6=3 6,6=2

0,1=1 1,1=2 2,2=5 60=1 2,3=0 4,2=2 3,6=5 4,6=4 6,5=3

0,2=1 1,2=3 3,0=1 2,4=2 4,3=6 4,4=3 5,4=0

0,3=1 1,3=4 3,1=4 2,5=4 5,2=4 5,3=2 5,5=5

0,4=1 1,4=5 4,0=1 2,6=6 6,1=0 6,3=5 6,4=4

0,5=1 1,5=6 4,1=5 3,2=0 6,2=6

0,6=1 2,0=1 5,0=1 3,3=3

r53

r55

r54

r51

r50

r45

r44

r43

r42

r41

r35

r34

r33

r32

r31

r30

r25

r24

r23

r22 r21

r20

r15 r14

r13

r12

r11

r10

r05

r03

r04

r02

r01 r00

e1

e0

e2

e5 e4

e3

r40

r52

368 Respuestas, introducción a los lenguajes formales

e2

r20 r21 r22 r23 r24 r25

0,0=2 1,0=2 2,2=6 1,5=0 4,2=3 2,6=0 6,2=0 4,5=1 5,6=4 6,6=3

0,1=2 1,1=3 3,0=2 1,6=1 5,1=0 3,4=0 6,3=6 4,6=5 6,5=4

0,2=2 1,2=4 3,1=5 2,3=1 5,2=5 3,5=3 5,4=1

0,3=2 1,3=5 4,0=2 2,4=3 6,1=1 3,6=6 5,5=6

0,4=2 1,4=6 4,1=6 2,5=5 4,3=0 6,4=5

0,5=2 2,0=2 5,0=2 3,2=1 4,4=4

0,6=2 2,1=4 6,0=2 3,3=4 5,3=3

e3

r30 r31 r32 r33 r34 r35

0,0=3 1,0=3 3,1=6 1,4=0 3,2=2 2,6=1 3,6=0 5,5=0 6,6=4

0,1=3 1,1=4 4,0=3 1,5=1 3,3=5 3,4=1 4,5=2 5,6=5

0,2=3 1,2=5 5,0=3 1,6=2 4,1=0 3,5=4 4,6=6 6,5=5

0,3=3 1,3=6 6,0=3 2,2=0 4,2=4 4,3=1 5,4=2

0,4=3 2,0=3 2,3=2 5,1=1 4,4=5 6,3=0

0,5=3 2,1=5 2,4=4 5,2=6 5,3=4 6,4=6

0,6=3 3,0=3 2,5=6 6,1=2 6,2=1

e4

r40 r41 r42 r43 r44 r45

0,0=4 1,0=4 5,0=4 1,3=0 3,1=0 2,5=0 5,3=5 3,6=1 46=0 6,6=5

0,1=4 1,1=5 6,0=4 1,4=1 3,2=3 2,6=2 6,2=2 4,5=3 55=1

0,2=4 1,2=6 1,5=2 3,3=6 3,4=2 5,4=3 56=6

0,3=4 2,0=4 1,6=3 4,1=1 3,5=5 6,3=1 64=0

0,4=4 2,1=6 2,2=1 4,2=5 4,3=2 65=6

0,5=4 3,0=4 2,3=3 5,1=2 4,4=6

0,6=4 4,0=4 2,4=5 6,1=3 5,2=0

e5

r20 r21 r22 r23 r24 r25

0,0=5 1,0=5 1,2=0 2,3=4 6,1=4 2,5=1 5,3=6 3,6=2 46=1 5,6=0

0,1=5 1,1=6 1,3=1 2,4=6 2,6=3 6,2=3 4,4=0 55=2 6,6=6

0,2=5 2,0=5 1,4=2 3,1=1 3,3=0 4,5=4 64=1

0,3=5 3,0=5 1,5=3 3,2=4 3,4=3 5,4=4

0,4=5 4,0=5 1,6=4 4,1=2 3,5=5 6,3=2

0,5=5 5,0=5 2,1=0 4,2=6 4,3=3

0,6=5 6,0=5 2,2=2 5,1=3 5,2=1

Respuestas, introducción a los lenguajes formales 369

Tabla de transiciones para las funciones de estado siguiente δ y salida σ.

δ σ

e0 e1 e2 e3 e4 e5 e0 e1 e2 e3 e4 e5

00 e0 e0 e0 e0 e0 e0 0 1 2 3 4 5

01 e0 e0 e0 e0 e0 e0 0 1 2 3 4 5

02 e0 e0 e0 e0 e0 e0 0 1 2 3 4 5

03 e0 e0 e0 e0 e0 e0 0 1 2 3 4 5

04 e0 e0 e0 e0 e0 e0 0 1 2 3 4 5

05 e0 e0 e0 e0 e0 e0 0 1 2 3 4 5

06 e0 e0 e0 e0 e0 e0 0 1 2 3 4 5

10 e0 e0 e0 e0 e0 e0 0 1 2 3 4 5

11 e0 e0 e0 e0 e0 e0 1 2 3 4 5 6

12 e0 e0 e0 e0 e0 e1 2 3 4 5 6 0

13 e0 e0 e0 e0 e1 e1 3 4 5 6 0 1

14 e0 e0 e0 e1 e1 e1 4 5 6 0 1 2

15 e0 e0 e1 e1 e1 e1 5 6 0 1 2 3

16 e0 e1 e1 e1 e1 e1 6 0 1 2 3 4

20 e0 e0 e0 e0 e0 e0 0 1 2 3 4 5

21 e0 e0 e0 e0 e0 e1 2 3 4 5 6 0

22 e0 e0 e0 e1 e1 e1 4 5 6 0 1 2

23 e0 e1 e1 e1 e1 e1 6 0 1 2 3 4

24 e1 e1 e1 e1 e1 e1 1 2 3 4 5 6

25 e1 e1 e1 e1 e2 e2 3 4 5 6 0 1

26 e1 e1 e2 e2 e2 e2 5 6 0 1 2 3

30 e0 e0 e0 e0 e0 e0 0 1 2 3 4 5

31 e0 e0 e0 e0 e1 e1 3 4 5 6 0 1

32 e0 e1 e1 e1 e1 e1 6 0 1 2 3 4

33 e1 e1 e1 e1 e1 e2 2 3 4 5 6 0

34 e1 e1 e2 e2 e2 e2 5 6 0 1 2 3

35 e2 e2 e2 e2 e2 e2 1 2 3 4 5 5

36 e2 e2 e2 e3 e3 e3 4 5 6 0 1 2

40 e0 e0 e0 e0 e0 e0 0 1 2 3 4 5

41 e0 e0 e0 e1 e1 e1 4 5 6 0 1 2

42 e1 e1 e1 e1 e1 e1 1 2 3 4 5 6

43 e1 e1 e2 e2 e2 e2 5 6 0 1 2 3

44 e2 e2 e2 e2 e2 e3 2 3 4 5 6 0

45 e2 e3 e3 e3 e3 e3 6 0 1 2 3 4

46 e3 e3 e3 e3 e4 e4 3 4 5 6 0 1

50 e0 e0 e0 e0 e0 e0 0 1 2 3 4 5

51 e0 e0 e1 e1 e1 e1 5 5 0 1 2 3

370 Respuestas, introducción a los lenguajes formales

52 e1 e1 e1 e1 e2 e2 3 4 5 6 0 1

53 e2 e2 e2 e2 e2 e2 1 2 3 4 5 6

54 e2 e3 e3 e3 e3 e3 6 0 1 2 3 4

55 e3 e3 e3 e4 e4 e4 4 5 6 0 1 2

56 e4 e4 e4 e4 e4 e5 2 3 4 5 6 0

60 e0 e0 e0 e0 e0 e0 0 1 2 3 4 5

61 e0 e1 e1 e1 e1 e1 6 0 1 2 3 4

62 e1 e1 e2 e2 e2 e2 5 6 0 1 2 3

63 e2 e2 e2 e3 e3 e3 4 5 6 0 1 2

64 e3 e3 e3 e3 e4 e4 3 4 5 6 0 1

65 e4 e4 e4 e4 e4 e5 2 3 4 5 6 0

66 e5 e5 e5 e5 e5 e5 1 2 3 4 5 6

Como se trata de una división primera (560134(7) entre 351(7)). Realmente es una serie de

multiplicaciones primero y restas después. Como 351(7) está cabe una sola vez en 560(7) , por lo tanto

se deberá multiplicar 351(7) por 1 y restarse a 560 (7). Usando las correspondientes funciones de

salida y de entrada.

δ (e0, 11) = e0 σ(e0, 11) = 1

δ (e0, 15) = e0 σ(e0, 15) = 5

δ (e0, 13) = e0 σ(e0, 13) = 3

Posteriormente se lleva a cabo la resta de 560(7) menos 351(7)). , en donde la máquina de estados

finitos tiene las siguientes características:

Elementos de los conjuntos E, A y B

E={e0, e1},

A={00, 01, 02, 03, 04, 05, 06, 10, 11, 12, 13, 14, 15, 16, 20, 21, 22, 23, 24, 25, 26, 30, 31, 32,

33, 34, 35, 36, 40, 41, 42, 43, 44, 45, 46, 50, 51, 52, 53, 54, 55, 56, 60, 61, 62, 63, 64, 65, 66}

y

B={0, 1, 2, 3, 4, 5, 6}.

Estado inicial.

s=e0.

Respuestas, introducción a los lenguajes formales 371

Diagrama de transiciones.

La resta de 560(7) menos 351(7).

δ (e0, 01) = e1 σ(e0, 01) = 6

δ (e1, 65) = e0 σ(e0, 65) = 0

δ (e0, 53) = e0 σ(e0, 53) = 2

δ (e0, 03) = e0 σ(e0, 53) = 0

Se multiplica 0351(7). Por 3:

δ (e0, 13) = e0 σ(e0, 13) = 3

δ (e0, 53) = e2 σ(e0, 53) = 1

δ (e2, 33) = e1 σ(e2, 33) = 4

δ (e1, 03) = e0 σ(e1, 03) = 1

Resta de: 2061(7) menos 1413(7).

δ (e0, 13) = e1 σ(e0, 13) = 5

δ (e1, 61) = e0 σ(e0, 61) = 4

δ (e0, 04) = e1 σ(e0, 04) = 3

δ (e1, 21) = e0 σ(e1, 21) = 0

Se multiplica 0351(7). Por 6:

δ (e0, 16) = e0 σ(e0, 16) = 6

δ (e0, 56) = e4 σ(e0, 56) = 2

δ (e4, 36) = e3 σ(e4, 36) = 1

δ (e3, 06) = e0 σ(e3, 06) = 3

Resta de: 3453(7) menos 3126(7).

e1 e0

0,0=0 3,1=2 4,4=0 6,0=6 1,0=1 3,2=1 5,0=5 6,1=5

1,1=0 3,3=0 5,1=4 6,2=4

2,0=2 4,0=4 5,2=3 6,3=3 2,1=1 4,1=3 5,3=2 6,4=2

2,2=0 4,2=2 5,4=1 6,5=1

3,0=3 4,3=1 5,5=0 6,6=0

0,1=6 1,3=5 2,6=3

0,2=5 1,4=4 3,4=6 0,3=4 1,5=3 3,5=5

0,4=3 1,6=2 3,6=4

0,5=2 2,3=6 4,5=6 0,6=1 2,4=5 4,6=5

1,2=6 2,5=4 5,6=6

0,6=0 3,2=0 5,1=3 6,2=3

1,0=0 4,0=3 5,2=2 6,3=2 2,0=1 4,1=2 5,3=1 6,4=1

2,1=0 4,2=1 5,4=0 6,5=0

3,0=2 4,3=0 6,0=5 6,6=6 3,1=1 5,0=4 6,1=4

0,0=6 1,2=5 2,4=4 4,4=6 0,1=5 1,3=4 2,5=3 4,5=5

0,2=4 1,4=3 2,6=2 4,6=4

0,3=3 1,5=2 3,3=6 5,5=6 0,4=2 1,6=1 3,4=5 5,6=5

0,5=1 2,2=6 3,5=4

1,1=6 2,3=5 3,6=3

372 Respuestas, introducción a los lenguajes formales

δ (e0, 36) = e1 σ(e0, 36) = 4

δ (e1, 52) = e0 σ(e1, 52) = 2

δ (e0, 41) = e0 σ(e0, 41) = 3

δ (e0, 33) = e0 σ(e0, 33) = 0

Se multiplica 0351(7). Por 6:

δ (e0, 16) = e0 σ(e0, 16) = 6

δ (e0, 56) = e4 σ(e0, 56) = 2

δ (e4, 36) = e3 σ(e4, 36) = 1

δ (e3, 06) = e0 σ(e3, 06) = 3

Resta de: 3244(7) menos 3126(7).

δ (e0, 46) = e1 σ(e0, 46) = 5

δ (e1, 42) = e0 σ(e1, 42) = 1

δ (e0, 21) = e0 σ(e0, 21) = 1

δ (e0, 33) = e0 σ(e0, 33) = 0

De tal manera que el resultado de dividir: 560134(7) entre 351(7)., es igual a 13366(7) resto 115(7)

9.21.-

a)

Gramática:

T={a, b}

N = {q0, q1, q2, q3, q4}

s= q0

Composiciones:

q0 aq4 q2 aq0 q4 aq1 q2 a

q0 bq0 q2 bq3 q4 bq2 q3 b

b

b

a

a b

a

a

b a

b

q2

q1

q3

q0

q4

AF equivalente

Respuestas, introducción a los lenguajes formales 373

q1 aq1 q3 aq1 q0 b q0 a

q1 bq0 q3 bq4 q1 b

b)

Gramática:

T={a, b}

N = {q0, q1, q2, q3, q4}

s= q0

Composiciones:

q0 aq2 q2 aq1 q4 aq0 q3 a

q0 bq1 q2 bq4 q4 bq1 q4 a

q1 aq0 q3 aq0 q0 a q2 b

q1 bq3 q3 bq4 q1 a q3 b

9.22.-

a)

a,1

b,1

b,0

a,1

a,1 b,0

b,0

a,1

b,1

q3

a,0 q1 q0

q4

q2 Máquina de estados

finitos equivalente

c,0

a,0

a,1

b,0

c,0

a,0

b,1

b,1

c,1

a,1

b,1

q0

c,1

q3

q1 q2 Máquina de estados

finitos equivalente

374 Respuestas, introducción a los lenguajes formales

Gramática:

T={a, b, c}

N = {q0, q1, q2, q3}

s= q0

Composiciones:

q0 aq1 q1 cq3 q3 bq2 q2 a

q0 bq3 q2 aq2 q3 cq1 q2 b

q0 cq0 q2 bq3 q0 b q2 c

q1 aq2 q2 cq0 q1 a q3 b

q1 bq1 q3 aq0 q1 c q3 c

b)

Gramática:

T={a, b}

N = {q0, q1, q2, q3, q4}

s= q0

Composiciones:

q0 aq4 q2 aq1 q4 aq1 q3 a

q0 bq1 q2 bq3 q4 bq2 q4 a

q1 aq3 q3 aq2 q0 b q4 b

q1 bq0 q3 bq0 q2 a

b

b

b

a

a

a

a b

a b

q0

q4

q3

q1 q2

Respuestas, introducción a los lenguajes formales 375

9.23.-

a) Para la palabra xxy la MT lleva a cabo el siguiente recorrido:

E={ e0, e1, e2, e3}

∑={x, y}

A={x, y, b}

F={ e3}

s = e0.

La función de transición δ tiene las siguientes composiciones:

δ (e0, x) = (e0, x, D) δ (e1, b) = (e2, b, I) δ (e2, b) = (e3, b, D)

δ (e0, y) = (e1, y, D) δ (e2, x) = (e2, x, I)

δ (e1, y) = (e1, y, D) δ (e2, y) = (e2, y, I)

b x x y b b x x y b b x x y b

e0 e0 e0

b x x y b B x x y b b x x y b

e1 e2 e2

b x x y b B x x y b b x x y b

e2 e2 e2

O bien:

be0xxybbxe0xybbxxe0ybbxxye1bbxxe2ybbxe2xybbe2xxyb

e2bxxybbe3xxyb

Para la palabra xxyx

b x x y x b b x x y x b b x x y x b

e0 e0 e0

b x x y b

e3

Como e3 es un estado de

aceptación, entonces se dice que

xxy L

376 Respuestas, introducción a los lenguajes formales

b) La MT es.

E={ e0, e1, e2, e3}

∑={x}

A={x, b}

F={ e3}

s = e0.

La función de transición δ tiene las siguientes composiciones:

δ (e0, x) = (e1, x, D) δ (e2, x) = (e2, x, I)

δ (e1, x) = (e0, x, D) δ (e2, b) = (e3, b, D)

δ (e0, b) = (e2, b, I)

Para xxxx la MT realiza el siguiente recorrido:

b x x x x b b x x x x b b x x x x b

e0 e1 e0

b x x x x b b x x x x b b x x x x b

e1 e0 e2

b x x x x b b x x x x b b x x x x b

e2 e2 e2

b x x y x b

e1

Como δ (e1, y) no está definida, la

MT se detiene en un estado no

aceptado, por lo tanto xxyxL

b x x x x b b x x x x b

e2 e3

Como e3 es un estado de

aceptación xxxxL

Respuestas, introducción a los lenguajes formales 377

Para xxx la MT realiza el siguiente recorrido:

b x x x b B x x x b b x x x b

e0 e1 e0

c) La MT es.

E={ e0, e1, e2, e3}

∑={x}

A={x, b}

F={ e3}

s = e0.

La función de transición δ tiene las siguientes composiciones:

δ (e0, x) = (e0, x, D) δ (e1, b) = (e2, b, I) δ (e2, x) = (e2, x, I)

δ (e0, y) = (e0, y, D) δ (e2, z) = (e2, z, I) δ (e2, b) = (e3, b, D)

δ (e0, z) = (e1, z, D) δ (e2, y) = (e2, y, I)

Para xyyz la MT realiza el siguiente recorrido:

b x y y z b b x y y z b b x y y z b

e0 e0 e0

b x y y z b b x y y z b b x y y z b

e0 e1 e2

b x y y z b b x y y z b b x y y z b

e2 e2 e2

Como δ (e1, b) no está definida, la MT

se detiene en e1. Pero como no es estado

de aceptación xxxL

b x x x b

e1

b x y y z b b x y y z b

e2 e3

Como e3 es un estado de

aceptación xyyzL

378 Respuestas, introducción a los lenguajes formales

Para xzz la MT realiza el siguiente recorrido:

b x z z b b x z z b b x z z b

e0 e0 e1

Pero δ (e1, z) no está definida ni tampoco e1 es estado de aceptación xzzL.

9.24.-

a)

Para la palabra yzy la MT lleva a cabo el siguiente recorrido:

E={ e0, e1, e2, e3, e4, e5}

∑={x, y, z}

A={x, y, z, b}

F={ e5}

s = e0.

La función de transición δ tiene las siguientes composiciones:

δ (e0, y) = (e1, y, D) δ (e2, y) = (e3, y, D) δ (e4, z) = (e4, z, I)

δ (e1, x) = (e1, x, D) δ (e3, b) = (e4, b, I) δ (e4, x) = (e4, x, I)

δ (e1, z) = (e2, z, D) δ (e4, y) = (e4, y, I) δ (e4, b) = (e5, b, D)

b y z y b b y z y b b y z y b

e0 e1 e2

b y z y b b y z y b b y z y b

e3 e4 e4

b y z y b b y z y b b y z y b

e4 e4 e5

Como e5 es un estado de aceptación, entonces se dice que yzy L

Respuestas, introducción a los lenguajes formales 379

O bien:

be0yzybbye1zybbyze2ybbyzye3bbyze4ybbye4zybbe4yzyb

e4byzybbe5yzyb

Para la palabra yxxzy

b y x x z y b b y x x z y b b y x x z y b

e0 e1 e1

b y x x z y b b y x x z y b b y x x z y b

e1 e2 e3

b y x x z y b b y x x z y b b y x x z y b

e4 e4 e4

b y x x z y b b y x x z y b b y x x z y b

e4 e4 e4

Como e5 es un estado de aceptación, entonces se dice que yxxzy L

O bien:

be0yxxzybbye1xxzybbyxe1xzybbyxxe1zybbyxxze2ybbyxxzye3b byxxze4yb

byxxe4zybbyxe4xzybbye4xxzybbe4yxxzyb e4byxxzybbe5yxxzyb

Para la palabra yzyz

b y z y z b b y z y z b b y z y z b

e0 e1 e2

b y x x z y b

e5

380 Respuestas, introducción a los lenguajes formales

b y z y z b

e3

Como δ (e3, z) no está definida, la MT se detiene en un estado no aceptado (e3), por lo tanto

yzyzL.

b)

Para la palabra zxy la MT lleva a cabo el siguiente recorrido:

E={ e0, e1, e2, e3, e4, e5}

∑={x, y, z}

A={x, y, z, b}

F={ e5}

s = e0.

La función de transición δ tiene las siguientes composiciones:

δ (e0, z) = (e1, z, D) δ (e2, z) = (e2, z, D) δ (e3, b) = (e4, b, I)

δ (e1, x) = (e2, x, D) δ (e3, y) = (e3, y, D) δ (e4, y) = (e4, y, I)

δ (e2, y) = (e3, y, D) δ (e3, z) = (e2, z, D) δ (e4, z) = (e4, z, I)

δ (e4, x) = (e4, x, I) δ (e4, b) = (e5, b, D)

b z x y b b z x y b b z x y b

e0 e1 e2

b z x y b b z x y b b z x y b

e3 e4 e4

b z x y b b z x y b b z x y b

e4 e4 e5

Como e5 es un estado de aceptación, entonces se dice que zxy L

Respuestas, introducción a los lenguajes formales 381

O bien:

be0zxybbze1xybbzxe2ybbzxye3bbzxe4ybbze4xybbe4zxyb e4bzxyb

be5zxyb

Para la palabra zxxyy, la MT tiene las siguientes operaciones:

b z x x y y b b z x x y y b b z x x y y b

e0 e1 e2

Como δ (e2, x) no está definida, la MT se detiene en un estado no aceptado (e2), por lo tanto

yxxyyL.

Para la palabra zxyyx, la MT tiene las siguientes operaciones:

b z x y y x b b z x y y x b b z x y y x b

e0 e1 e2

b z x y y x b b z x y y x b

e3 e3

Como δ (e3, x) no está definida, la MT se detiene en un estado no aceptado (e3), por lo tanto

zxyyxL.

c)

La MT que acepta el lenguaje L={xny

n / n≥1} es:

E={ e0, e1, e2, e3, e4, e5, e6, e7, e8, e9, e10} Conjunto de estados de la MT.

∑={x, y} Alfabeto de entrada.

A={x, y, c, d, b} Alfabeto de la cinta.

F={ e10} Estado de aceptación.

s = e0. Estado inicial.

La función de transición δ tiene las siguientes composiciones para cambiar las letras “x” por “c” y

las letras “y” por “d”.

δ (e0, x) = (e1, c, D) δ (e1, d) = (e2, d, I) δ (e3, x) = (e3, x, I)

382 Respuestas, introducción a los lenguajes formales

δ (e1, x) = (e1, x, D) δ (e2, y) = (e3, d, I) δ (e1, b) = (e2, b, I)

δ (e1, y) = (e1, y, D) δ (e3, y) = (e3, y, I) δ (e3, c) = (e0, c, D)

Considerar la palabra xxyy cuya trayectoria en la MT es como se muestra:

b x x y y b b c x y y b b c x y y b

e0 e1 e1

b c x y y b b c x y y b b c c y y b

e1 e1 e2

b c x y d b b c x y d b b c x y d b

e3 e3 e3

b c x y d b b c c y d b b c c y d b

e0 e1 e1

b c c y d b b c c d d b b c c d d b

e2 e3 e0

Una vez que han sido cambiadas todas las “x” por “c” y todas las “y” por “d” regresamos al

principio de la cadena con las siguientes composiciones adicionales:

δ (e0, d) = (e4, d, I)

δ (e4, c) = (e4, c, I)

δ (e4, b) = (e5, b, D)

b c c d d b b c c d d b b c c d d b

e4 e4 e4

Respuestas, introducción a los lenguajes formales 383

b c c d d b

e5

Ahora se deben cambiar las “c” por “x” y las “d” por “y” para no perder la cadena inicial.

A la función de transición δ se deben adicionar las siguientes composiciones:

δ (e5, c) = (e6, x, D) δ (e6, y) = (e7, y, I) δ (e8, c) = (e8, c, I)

δ (e6, c) = (e6, c, D) δ (e7, d) = (e8, y, I) δ (e6, b) = (e7, b, I)

δ (e6, d) = (e6, d, D) δ (e8, d) = (e8, d, I) δ (e8, x) = (e5, x, D)

Considerar que se parte de la palabra en donde se cambiaron las letras “x” por las letras “c” y el

carácter “y” por el carácter “d” anterior ccdd cuya trayectoria en la MT es como se muestra:

b c c d d b b x c d d b b x c d d b

e5 e6 e6

b c c d d b b x c d d b b x c d d b

e6 e6 e7

b x c d y b b x c d y b b x c d y b

e8 e8 e8

b x c d y b b x x d y b b x x d y b

e5 e6 e6

b x c d y b b x x y y b b x x y y b

e7 e8 e5

Una vez que han sido cambiadas todas las “c” por “x” y todas las “d” por “y” regresamos al

principio de la cadena con las siguientes composiciones adicionales:

384 Respuestas, introducción a los lenguajes formales

δ (e5, y) = (e9, y, I)

δ (e9, x) = (e9, x, I)

δ (e9, b) = (e10, b, D)

b x x y y b b x x y y b b x x y y b

e9 e9 e9

b x x y y b

e10

Como e10 es un estado de aceptación, entonces se dice que xxyy L={xny

n / n≥1}.

d)

Para la palabra xxyyxz la MT lleva a cabo el siguiente recorrido:

E={ e0, e1, e2, e3, e4, e5}

∑={x, y, z}

A={x, y, z, b}

F={ e5}

s = e0.

La función de transición δ tiene las siguientes composiciones:

δ (e0, x) = (e1, x, D) δ (e2, b) = (e3, b, I) δ (e3, b) = (e4, b, D)

δ (e1, x) = (e1, x, D) δ (e3, x) = (e3, x, I)

δ (e1, y) = (e1, y, D) δ (e3, y) = (e3, y, I)

δ (e1, z) = (e2, z, D) δ (e3, z) = (e3, z, I)

b x x y y x z b b x x y y x z b b x x y y x z b

e0 e1 e1

b x x y y x z b b x x y y x z b b x x y y x z b

e1 e1 e1

Respuestas, introducción a los lenguajes formales 385

b x x y y x z b b x x y y x z b b x x y y x z b

e2 e3 e3

b x x y y x z b b x x y y x z b b x x y y x z b

e3 e3 e3

b x x y y x z b b x x y y x z b b x x y y x z b

e3 e3 e4

Como e4 es un estado de aceptación, entonces se dice que xxyyxz L. Esta MT acepta tambien las

cadenas: xz, xyz, xyyz, entre otras, pero no acepta las siguientes cadenas: yxxz, xyzz, xzx, zyx, entre

otras.