Máquinas

de
Estado Finito
 ¿Qué es una máquina de
estado finito? Máquinas Equivalentes.
01 Definiciones y 03 Optimizacíon
Definiciones y
teoremas teoremas

Ejemplos de Aplicación Ejemplos

02 Ejercicios Resueltos 04 Máquinas de estado
finito en la vida diaria
Las máquinas de estado finito en
la tecnología
Introduccíon a las máquinas de estado finito
“Estos objetos matemáticos son los modelos para los ordenadores digitales y
constituyen una importante herramienta en el diseño de circuitos físicos
secuenciales, en el estudio de los lenguajes formales y de compiladores e
intérpretes de lenguajes de programación”
 Todas las máquinas de estado finito tienen un
conjunto de estados, incluido el estado inicial, un
alfabeto fuente y una función de transición que a
cada pareja de estado y dato de entrada le asigna el
estado siguiente.
Algunas máquinas de estado finito producen un
símbolo como dato de salida para cada transición y
pueden utilizarse para modelar gran variedad de
máquinas, entre las que se incluyen las máquinas
expendedoras, los semáforos, los sumadores binarios
y los reconocedores de lenguajes.
¿Qué es una máquina
de estado finito? 01
Definiciones y teoremas
Definición de una máquina de estado finito

Una máquina de estado finito es una tupla M = (S, A, t),

donde S y A son conjuntos finitos no vacíos y t: S × A →
S es una función. Los elementos de S se llaman estados.
Hay un elemento distinguido de S llamado el estado
inicial. El conjunto A se denomina alfabeto de entrada, los
elementos se denominan letras. La función t se llama
transición de estado función.
Una máquina de estado finito (o máquina secuencial
completa) M consta de seis partes:

 Un conjunto finito A de símbolos de entrada.

 Un conjunto finito S de estados internos.
 Un conjunto finito Z de símbolos de salida.
 Un estado inicial s 0 en S.
 Una función f de estado siguiente de S × A en S.
 Una función g de salida de S × A en Z.

Cuando se indican las seis partes de una máquina M se

denota por M = M(A, S, Z, s 0 , f, g).
 ℕ = {1, 2, 3, 4, …}
Los estados se
denotan por
Números naturales

Notaciones
Importantes El estado inicial se
denota por 0

El alfabeto es un
subconjunto del
alfabeto romano.
Dos maneras usuales de representar una MEF son: el
diagrama de estados y la tabla de estados. El diagrama de
estados es una representación sagital cuyos vértices son
los estados internos de la máquina; se dibuja una flecha de
un estado e a otro estado e′ si para alguna entrada x ocurre
que ce(x, e) = e′. La flecha lleva doble ponderación: la
entrada x y la respectiva salida s = co(x, e).
Pongamos I = {0, 1}, O = {a, b} y E = {e0 , e1 , e2 }. Cualquier par de aplicaciones ce :
I × E −→ E , co : I × E −→ O completa la definición de una máquina con alfabeto I, O y 3-estados
internos e0 , e1 , e2 . En la tabla siguiente se da un par ce, co.

(0, e0) (1, e0) (0, e1) (1, e1) (0, e2) (1, e1)

Ce e1 e0 e2 e1 e0 e2

co a b b a b a
La tabla de estados es una tabulación simultánea de las dos aplicaciones, la de cambio de estados
y la de salidas. Para una máquina M = [I, O, E , ce, co] que tenga I = {a1 , a2 , . . . , aj , . . . , an , } y
E = {e1 , e2 , . . . , ei , . . . , em }, una manera de organizar la tabla es la siguiente.

M ce coe
a1 . . . aj . . . an 1 . . . ei . . . em

e1 ce(a1,e1)...ce(aj,e1)...ce(an,e1) co(a1,e1)...co(aj,e1)...co(an,e1)

ei ce(a1,ei)...ce(aj,ei)...ce(an,ei) co(a1,ei)...co(aj,ei)...co(an,ei)

em ce(a1,em)...ce(aj,em)...ce(an,em) co(a1,em)...co(aj,em)...co(an,em)
 ¿Cómo funcionan las máquinas de estado finito?

Pensamos en la máquinas de estado finito M= (S,A,t)

como una descripción formal de un determinado
dispositivo que opera de manera discreta. En cualquier
momento se supone que está en algún estado s ∈ S. La
máquina lee una letra de entrada a ∈ A. Entonces hace
transición al estado t(s,a). Después de eso, la máquina
está lista para aceptar otra letra de entrada. El trabajo
de una máquina tiene el siguiente aspecto: introducir la
palabra w, es decir, una secuencia a1a2...an de letras
desde A. Luego configuramos la máquina en el estado
inicial s0 y comience a ingresar la palabra w en él (letra
por letra). El trabajo de la máquina resulta en una
secuencia de estados s0,s1,...,sn, que describe el trabajo
interno del dispositivo
Características de una máquina de estado

 No puede estar en más de un estado por vez.

 El estado en el que se encuentra se denomina

estado actual.

 El cambio de un estado a otro se denomina

transición entre estados.

 Son muy útiles en el diseño de protocolos de

comunicación.

 Existen dos tipos de máquinas de estados:

Moore y Mealy.
Ejemplos De
Aplicación 02
Ejercicios Resueltos
 Aplicaciones
Ejercicio 8

Ejercicio 1
Ejercicio 7

Ejercicio 2
Ejercicio 6

Ejercicio 5 Ejercicio 3

Ejercicio 4
Ejercicio 1
Suponga que la palabra de entrada es w = a-b-a-a-b. El trabajo interno de la máquina en esta
entrada está determinado por una ruta en el gráfico tal que la ruta comienza en el estado inicial 0 y
la palabra w se lee en las etiquetas a lo largo del camino
a b
0 1 2

1 2 1

2 0 0

a b a a b
0 1 1 2 0 2
Ejercicio 2
Cuando el usuario ingrese 101, el cajero automático le devolverá el dinero. Validar si el usuario
comete un error al ingresar la entrada a = [101]

Estado X Estado Salida

Inicial Final
e0 0 e0 0
e0 1 e1 0
e1 0 e2 0
e1 1 e1 0
e2 0 e2 0
e2 1 e0 1
Ejercicio 3
• S = { s1, s2 , … , sm} es un conjunto finito de nodos.
• Σ : es un alfabeto finito de etiquetas.
• A : es un conjunto finito de aristas etiquetadas que unen nodos.
• sk S ∈ : es el estado inicial.

S = {1,2,3}
Σ = {a , b}
A = {(1,a, 2) ,(2,b,3),(3,a,1) ,(1,b,3)}
Sk = 1
Ejercicio 4
Dada la FSM siguiente, encuentre las trazas

Las trazas de esta FSM son:

• {a, b, a} correspondiente a 1, 2, 3, 1
• {b, a} correspondiente a 1, 3, 1
• {a, b, a, b, a} correspondiente a 1, 2, 3, 1, 3, 1
• {b, a, a, b, a} correspondiente a 1, 3, 1, 2, 3, 1
• {b, a, b, a, ... , b, a} 1, 3, 1, 3, … , 1, 3
• Etc…
Ejercicio 5
Se quiere diseñar una máquina de estado finito que efectúe suma binaria en serie. Las entradas
posibles son los pares {00, 01, 10, 11}. Si la cifra de arrastre de la suma anterior es 0, el estado es
s0 y si la cifra de arrastre es 1, el estado es s1. El diagrama de estados sería:
Ejercicio 6 (Aplicación)
En una estación del Metro una máquina distribuye tiques sencillos a $600 pesos el tique. La
máquina acepta monedas de $100, $200, $500, $1000. Mediante una tabla, describa los diferentes
estados de la máquina y la salida.

Solución:
Se supondrá que la máquina se encuentra en el estado e 0 perteneciente a E en el tiempo t 0. Al
introducir una moneda en el tiempo t i la salida será g(x,es) donde es es el estado de la máquina en
el tiempo ti. A esta salida le sigue una transición de la máquina en el tiempo t i+1dado por f(x,es).
Los estados del conjunto E serán:

e0 = Estado inicial de la máquina sin introducir monedas.

e1 = La máquina recuerda la inserción de $100.
e2 = La máquina recuerda la inserción de $200.
e3 = La máquina recuerda la inserción de $300.
e4 = La máquina recuerda la inserción de $400.
e5 = La máquina recuerda la inserción de $500.
e6 = La máquina recuerda la inserción de $600 o más pesos.
La función f: E x A → E donde A = { n, 100, 200, 500, 1000, b } es la entrada donde n detalla el
hecho de no introducir monedas y b hundir botón para obtener el tiquete, se detalla en la siguiente
tabla:

n 100 200 500 1000 b

e0 e0 e1 e2 e5 e6 e0

e1 e1 e2 e3 e6 e6 e1
e2 e2 e3 e4 e6 e6 e2

e3 e3 e4 e5 e6 e6 e3
e4 e4 e5 e6 e6 e6 e4

e5 e5 e6 e6 e6 e6 e5
e6 e6 e6 e6 e6 e6 e0
En esta tabla por ejemplo, f(e0,500)=e5; lo que quiere decir que en el tiempo t siguiente la
máquina recordará que se le han introducido $500.

f(e3,200)=e5 , lo que significa que la máquina pasa del estado e 3; al estado e5 ; lo que quiere decir
que pasa de "recordar" que se le habrían introducido $300 a "recordar" que se le han introducido
$500.

f(e5,200)=e6 , lo que significa que la máquina pasa de "recordar" que se le habrían introducido
$500 a "recordar" que se le han introducido más de $600, en este caso, la función de salida se
diseñará para que devuelva $100 al comprador.

Al pulsar el botón, la máquina pasará al estado e 0; si el estado actual es e0 ó e6.

La función g:E x A → B es la función de salida, que se detalla en el siguiente cuadro:

g
n 100 200 500 1000 b

e0 n n n n 400 n

e1 n n n n 500 n
e2 n n n 100 600 n

e3 n n n 200 700 n
e4 n n n 300 800 n
e5 n n 100 400 900 n
e6 n 100 200 500 100 T
En esta tabla, g(e3,500) = 200, lo que significa que la máquina pasa de "recordar" que se le habían
introducido $300 a "recordar" $800 y por tanto devuelve $200. Como f(e 3,500)=e6, la máquina
pasa al estado e6 y por último, como g(e6,b)=T recibe el tique.

Como f(e6,b)=e0, la máquina retorna al estado inicial.

El conjunto de salida B será:

B = { n, 100, 200, 300, 400, 500, 600, 700, 800, 900, 1000, T}

acá: n significa que no hay salida.

T significa que se entrega el tique.

En esta tabla por ejemplo, f(e0,500)=e5; lo que quiere decir que en el tiempo t siguiente la
máquina recordará que se le han introducido $500.

f(e3,200)= e5 , lo que significa que la máquina pasa del estado e 3; al estado e5 ; lo que quiere decir
que pasa de "recordar" que se le habrían introducido $300 a "recordar" que se le han introducido
$500.

f(e5,200)= e6 , lo que significa que la máquina pasa de "recordar" que se le habrían introducido
$500 a "recordar" que se le han introducido más de $600, en este caso, la función de salida se
diseñará para que devuelva $100 al comprador.

Al pulsar el botón, la máquina pasará al estado e 0; si el estado actual es e0 ó e6.

Ejercicio 7
Diseñe una máquina de estado finito que produzca salida 1 siempre que vea 101; produce la salida
0 en caso contrario.

Acá A = {0, 1}, B = {0,1}. El estado inicial e 0 se mantendrá si la entrada es 0 y cambiará a e 1 si la

entrada es 1; es decir f(e0,0)= e0; f(e0,1)= e1. El estado e1 se mantendrá si la entrada es 1 y
cambiará a e2 si la entrada es 0; es decir f(e1,0)= e2; f(e1,1)= e1.

El estado e2 cambiará a e0 si la entrada es 0 y cambiará a e 1 si la entrada es 1 y acá la salida será 1.

Las demás salidas serán 0.
La tabla de transición de estados es:

0 1

e0 e0 e1
e1 e1 e1
e2 e2 e1
La tabla de salida es:

g
0 1
e0 0 0
e1 0 0

e2 0 1
Así por ejemplo, si la entrada es 101 la máquina hará lo
siguiente:

Al entrar 1 es estado cambia de e0 a e1 y la salida será 0.

Al entrar 0 el estado cambia de e1 a e2 y la salida es 0.
Al entrar 1 es estado cambia de e2 a e1 y la salida será 1.

Esta situación la podemos representar también, mediante

un diagrama de transición donde los vértices o círculos
serán los estados. El estado inicial se indica mediante una
flecha. Si una entrada produce un cambio de estado del
vértice ei al vértice ek, se traza una arista dirigida de e i a ek
y se etiqueta como x/s donde x es la entrada y s es la
salida. Si no hay cambio de estado, se traza un lazo
dirigido sobre el vértice que representa ese estado.

En el ejemplo anterior, el diagrama de transición es:

Ejercicio 8

ã = [0000]

s̃ = ?

e0 0 e2 0 e0 0 e2 0 e0
a b a b

s ̃ = [abab]
 Máquinas
Equivalentes
Optimización
03
Definiciones y teoremas
 Definición de Máquinas Equivalentes

El comportamiento secuencial de las máquinas puede ser descrito mediante aplicaciones. Dada una
MEF M = [I, O, E , ce, co] con estado inicial z, al proporcionarle una secuencia de entradas ã = [x 1 x2
. . . xk ] la MEF produce una secuencia de salidas s ̃ = [y1 y2 . . . yk ] y “sufre” una secuencia de
cambios internos ẽ = [zz1 z2 . . . zk ], según se muestra en el diagrama. Si el número k está fijo,
podemos mirar las secuencias [z, z1 z2 . . . zk ], [y1 y2 . . . yk ] como las imágenes respectivas de las
secuencias ã = [x1 x2 . . . xk ] bajo las aplicaciones siguientes:

cek+1 : Ik × E E k+1 dada por cek+1 ([x1 x2 . . . xk ], z) = [zz1 z2 . . . zk ]

cok : Ik × E Ok dada por cok ([x1 x2 . . . xk ], z) = [y1 y2 . . . yk ]

Nótese que esto puede hacerse para cada número entero positivo k. Si se tiene otra máquina ‘M = [I,
O, ‘E , ‘ce, ‘co] con los mismos alfabetos, al escoger un estado interno ‘z de ‘M , un estado interno z
de M y aplicar una secuencia de entradas ã = [x 1 x2 . . . xk ] a las dos máquinas, se obtendrán en cada
una de las dos las secuencias de entradas internas y de salidas.
En M las hemos denotados por:

[zz1 z2 . . . k ] = ce k+1 ([x1x2 . . . xk ], z) y [y1y2 . . . yk ] = cok ([x1x2 . . . xk ], z)

denotaremos las de ‘M por

[‘z ‘z1 ‘z2 . . . ‘zk ] = ‘ce k+1 ([x1x2 . . . xk ], ‘z) y [‘y1’y2 . . . ‘yk ] = ‘cok ([x1x2 . . . xk ], ‘z)
 Definición 4.2

 ‘M cubre a M (denotaremos por ‘M ⊒ M ) sii para cada estado finito e de M existe un estado
‘e de ‘M tal que ξ k (ã, e) = ξ k (ã, ‘e) para todo entero positivo k y para toda secuencia de
entradas ã = [x1 x2 . . . xk ] ∈ I

 ‘M es equivalente a M (denotado por ‘M eq M ) sii ‘M ⊒ M y M ⊒ ‘M

 M es una máquina minimal sii entre las máquinas que cubren a M no existe una que tenga
menos estados internos que M
 Teorema 4.1

1. La relación ⊒ es reflexiva y transitiva.

2. La relación eq es una relación de equivalencia.

Definición 4.3
Sea M = [I, O, E , ce, co] una MEF y sen e, e′ ∈ E . Diremos que:

e es r−equivalente a e′ (denotado por e EQr e′) sii para toda secuencia de entradas ã = [x 1 x
2 . . . xr ] ∈ Ir ocurre que ξ r (ã, e) = ξ r (ã, e′)

e es equivalente a e ′ (denotado por e EQ e′ sii e EQr e′ para todo entero positivo r.

 Teorema 4.3

 Para todo entero positivo r se cumple que:

(i) G(EQ r ) ⊃ G(EQ r+1 )

(ii) G(EQ r ) ∪ G(‘EQ r ) = E × E

 G(EQ) ∪ G(EQ) = E × E
Definición de un Homomorfismo
Un homomorfismo entre semigrupos S y T es una aplicación f : S → T que cumple f(ab) = f(a)f(b)
para todo a, b ∈ S. Si, además, S y T son monoides y se cumple f(1) = 1 entonces f se llamará un
homomorfismo de monoides. Se define monomorfismo, epimorfismo e isomorfismo de la forma
habitual


Un homomorfismo es un caso particular de sustitución en el que h : Σ −→ Γ∗
 Reducción de Autómatas

Estados equivalentes: Dado un autómata de estados finitos A=(Q,I,O,δ,λ), dos estados qi, qj ∈ Q
se dicen equivalentes ⇔ δ(qi,e) = δ(qj,e) ∀e ∈ I y λ(qi) =λ(qj). (β(qi,e) = β(qj,e) ∀e ∈ I) dos
estados equivalentes son indistinguibles
Ejemplos
04
Ejemplos de la vida diaria
 ¿SABIAS QUE?

En la vida diaria nos encontramos

con máquinas de estado finito. A
continuacion veremos algunos
ejemplos
 Máquina expendedora de golosinas

Vende chicles a 0.15$ y chocolates a 0.2$. La máquina acepta monedas de 5 y 10 centavos.

Cada vez que se introduce una moneda, la máquina emite un sonido (click), si dicha moneda
es de 5 centavos o, dos (dos clicks) si es de 10 centavos. Se tienen 2 botones selectores para
elegir la golosina deseada y uno de devolución que permite recuperar el dinero ingresado sino
se efectuó la entrega de ninguna golosina.

Se llega al diagrama de estados con los siguientes pasos:

 Definición del estado inicial del sistema
 Estando en el estado “cero”, el sistema es excitado mediante la inserción de una moneda.
Si la moneda es de 5 centavos, el sistema pasa al estado “cinco” y emite un “click”, por el
 contrario si la moneda es de 10 centavos se pasa al estado “diez” emitiendo un doble
“click”
Estando en el estado “cinco”, los estímulos que el sistema reconoce son:

 Monedas de 5 y 10 centavos, las cuales en caso de introducirse, ocasionan una transición

al estado “diez” o “quince”, respectivamente y, la emisión de 1 o 2 “clicks”, según
corresponda.
 Botón de devolución “dev”. En caso de oprimirse este botón, la máquina devuelve 5
centavos y vuelve al estado inicial “cero”
En la figura se aprecia el diagrama de estados completo de la máquina expendedora. En caso
de presionar el botón de “chicle”, estando en el estado “veinte” la máquina responde
entregando el chicle y además los 5 centavos de vuelto (“chicle” + “5”).
Semáforos
Maquina Expendedora
Ascensores
 Gracias
por su
Atención
 Biblografía

https://www.includehelp.com/basics/finite-automata.aspx
https://brilliant.org/wiki/finite-state-machines/
http://www.cse.chalmers.se/~coquand/AUTOMATA/book.pdf
https://issuu.com/esau1409/docs/esau_sanchez_ci16669954_-_revista_digital
https://www.monografias.com/docs114/maquinas-estado/maquinas-estado.shtml