Matemática Discreta - Ejercicios Propuestos

Ejercicios propuestos:

Sea M=(A,S,Z,F,G)una maquina de estado finito con alfabeto de entrada A={ +, x},conjunto de estados S={ S0, S1, S2},alfabeto de salida Z={0,1} y funciones F estados y G de salida definidas por la tabla de estados.

Estado a b a b

S0

S1

S2

S1 S2

S2 S1

S1 S0

0 0

1 0

1 0

Si el estado inicial es S0.

a)representar la maquina M mediante un diagrama.

b)si la cadena de entrada es: + x x + x + + x , encontrar la cadena de salida y la cadena de eestados.

Solución:

a) X/1

S0 +/1 S1

X/0 X/0 +/0 +/1

S2

b) M (S0, + x x + x + + x) = 11100100

2.Dada las siguientes maquinas de estado finito:

M F G

S 0 1 0 1

S1

S2

S3

S4

S5

S6 S2 S3

S1 S5

S2 S5

S6 S3

S2 S3

S4 S5 0 0

1 0

0 1

0 0

1 1

1 0

M’ F’ G’

S’ 0 1 0 1

T1

T2

T3

T4 T2 T3

T1 T4

T2 T4

T2 T3 0 1

1 0

1 1

0 1

a)Hacer los diagramas correspondientes a cada uno de ellos

solución

0/1 0/1

S1 0/0 S2 T1 0/0 T2

1/1 0/1 0/1

S3 1/1 S4 1/1 1/0 0/0

1/1 1/1 1/0 0/0 0/1

S5 1/0 S6 T3 1/1 T4

1/1

10. Determine: a/0

a)El conjunto finito A de simbolo de entrada. δ0 δ1

Un conjunto finito S de estados internos. a/1

Un conjunto finito S de estados internos. b/1 b/0 b/0 a/0

Un conjunto finito Z de simbolos de salida. δ2 a/0 δ3

b/0

b)la tabla que define las funciones de estado siguiente y de salida de la maquina

de estado finito descrito en forma grafica de la maquina de la figura.

c)Determine la cadena de salida para la cadena de entrada: bababbabaaa.En forma recursiva para la maquina dada.

solucion:

a) A= {a, b}

S= {δ0, δ1, δ2, δ3}

Z= {0, 1}

b) La tabla es:

Estado a b a b

δ0

δ1

...