estructuras discretas

Páginas: 2 (468 palabras) Publicado: 1 de diciembre de 2013
Capítulo 5
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...
Leer documento completo

Regístrate para leer el documento completo.

Estos documentos también te pueden resultar útiles

  • Estructuras Discretas
  • estructuras discretas
  • Estructuras discretas operadores logicos
  • Estructuras discretas ejercicios resueltos
  • Tarea Estructuras Discretas
  • Estructuras Discretas II 01
  • cuestionario estructuras discretas
  • Estructuras Discretas Proyecto

Conviértase en miembro formal de Buenas Tareas

INSCRÍBETE - ES GRATIS