estructuras discretas
Ejercicios Propuestos
1. Sea M = (A, S, Z, F, G) una máquina de estado finito con alfabeto de entrada
A = { + , x} , conjunto de estados S = { so , s1 , s2 } , alfabeto desalida Z = {0,1} y funciones F de estados y G de salida definidas por la tabla de estados:
S
F
G
+
x
+
x
so
s1
s2
1
0
s1
s2
s1
0
1
s2
s1
s0
1
0
Si elestado inicial es so :
a) Representar la máquina M mediante un diagrama.
b) Si la cadena de entrada es: + xx + x ++ x , encontrar la cadena de salida y la cadena de estados.
2. Dadaslas siguientes máquinas de estado finito:
M
F
G
M’
F’
G’
S
0
1
0
1
S’
0
1
0
1
S1
S2
S3
0
1
T1
T2
T3
0
1
S2
S1
S5
1
0
T2
T1
T3
1
0
S3
S2S5
1
1
T3
T2
T3
1
1
S4
S6
S3
0
1
T4
T2
T3
0
1
S5
S2
S3
1
1
S6
S4
S5
1
0
a) Hacer los diagramas correspondientes a cada una de las máquinasb) Establecer una función suryectiva que permita que la máquina M’ cubra a la máquina M y luego probar que la función encontrada es en realidad un cubrimiento.
3. Minimizar la máquina M =(A, S, Z, F, G) con alabeto de entrada A = {a,b,c} , conjunto de estados S = {1,2,3,4,5,6,7,8}, alfabeto de salida Z = {0,1,*} y funciones F, de estados, y G, de salida, definidas por la tablas:M
F
G
S
a
b
c
a
b
c
1
3
8
2
*
1
0
2
7
5
3
0
*
1
3
1
7
5
*
1
0
4
4
8
2
*
1
0
5
8
2
1
0
*
1
6
5
6
7
*
1
0
7
5
8
6
0
*
1
8
27
6
0
*
1
4. Dada la máquina de estados finitos:
M
F
G
S
a
b
c
a
b
c
0
2
2
7
0
0
0
1
2
2
6
1
1
0
2
2
3
2
1
1
0
3
2
2
3
1
1
0
4
86
8
0
0
1
5
5
5
8
1
1
0
6
4
1
4
0
0
1
7
7
7
9
0
0
0
8
5
5
8
1
1
0
9
9
7
9
0
0
0
Hallar M la máquina mínima de M y encontrar la función que define el...
Regístrate para leer el documento completo.