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.


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


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


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


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



s::= yA

A::= xC / xAB / Bxx / yx

B::= xBy / Ayy / yC / y

C::= x


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


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.


s::= 0A1 / 1A0

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


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


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


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}


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


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

+


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)


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}


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


b b

a q2 q0 q1

a


δ 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


b q3 q0 q1

q4

q2


d)

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

e)

Expresión regular = (b ab)*


δ 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


a

q3 q0 q1

q4

q2

q5


δ 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


b

q0 q1 q2


9.16.-

a)

Expresión regular = 100(10)*

b)

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


δ 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


0 q3 q0 q1

q4

q2


δ 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


0 0

1 q2 q0 q1

1


c)

Expresión regular = 01(01)*

d)

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


δ 1 0

q0 q1 q0

q1 q2 q1

q2 q2 q1

E = {q0, q1, q2}

F = {q2}

s = q0


δ 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


0 1

0 q2 q0 q1

1

q3


e)

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

0

1,0

1 1

1

1 0

0


0 q3 q0 q1

q4

q2


δ 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


0

q2 q0

q5

q1

q3 q4


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


δ 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


= {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


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}



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}



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}


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:



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, 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


Propiedades de los estados.

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

F = {e0, e2, e3, e4}

s = e0

b)


E = {q0, q1, q2}

F = {q1}

s = q0


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}



{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}



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}


Elemento a b

{e0} {e5}

{e1} {e1} {e0}

{e2} {e1}

{e3} {e5} {e0}

{e4} {e5} {e1}

{e5} {e1} {e3}

{e6} {e5} {e3}

En donde:


e1, e3, e5 y e6 son estados de

aceptación





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

F = {e0, e3, e5}

s = e0

c)


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}



E = {q0, q1, q2, q3}

F = {q3}

s = q0


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}



= {q1, q2}

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

= {q1, q2, q3}


= {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}



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}


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



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:


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




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

F = {e9, e13}

s = e0

d)


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}




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,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}


{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}


{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}



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}




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:


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




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


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.


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


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).


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)


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.




δ σ δ σ

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


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).


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)


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.




δ σ

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


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},


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.



δ σ

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


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)


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.



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


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



δ σ

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


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:


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.



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


δ (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


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

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

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

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


δ (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


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 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


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 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


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


b) La MT es.

E={ e0, e1, e2, e3}

∑={x}

A={x, b}

F={ e3}

s = e0.


δ (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


e1 e0 e2


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


aceptación xxxxL


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.


δ (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


e0 e1 e2


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


aceptación xyyzL


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.


δ (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


e3 e4 e4


e4 e4 e5

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


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


e1 e2 e3


e4 e4 e4


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


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.


δ (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


e3 e4 e4


e4 e4 e5

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


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)


δ (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


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:


δ (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.


δ (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


e1 e1 e1



e2 e3 e3


e3 e3 e3


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.

matematicas para la computacion jose jimenez murillo slideshare2

Engineering