Carrera:
Ingeniería de Minas
Profesora:
Adha Morales Moya
Curso:
Matemáticas Discretas
Trabajo Final:
“Máquina de estado finito con salida y sin salida”
Integrantes:
Rivera Revilla Diego
Neira Valdivia Yovani
Roque Cassa Eduardo
Hilari Apaza Coraly
Valdez Cruz Jonathan
Arequipa Perú
2013
1
INDICE
Introducción……………………………………………………………..3
Capítulo I………………………………………………………………..4
Máquinas de Estados Finitos………………………………………….5
Ejemplos…..…………..………………………………………….……..6
Tipos de Máquina con Salida………………………………...……….7
Máquina de Estados Finitos Sin Salida……………………...……….7
Ejemplos……….………………………………………………..……8
Ventajas de las Maquinas de Estado Finito………………...….…….9
Conjunto de Cadena…………………………………………………...10
2
Introducción
Se denomina máquina de estados a un modelo de comportamiento de un
sistema con entradas actuales sino también de las anteriores. Las maquinas
de estados se definen como un conjunto de estados que sirve de
intermediario en esta relación de entradas y salidas, haciendo que el
historial de señales de entrada determinada, para cada instante, un estado
para la maquina, de forma tal que la salida depende únicamente del estado
y las entradas actuales. Una maquina de estados se denomina maquina de
estados finitos si el conjunto de estados de la maquina es finito, este es el
único tipo de maquina de estados que podemos modelar en un computador
en la actualidad; debido a esto se suelen utilizar los términos maquina de
estados y maquina de estados finitos de forma intercambiable.
3
4
Máquina de Estado Finito con Salida
Definición : Las máquinas de este tipo se llaman máquinas de Mealy
porque fue G.H. Mealy, en 1955, el primero que las estudio. Hay otro
tipo importante de máquina de estado finito con salida, donde la salida
está determinada sólo Por el estado. Este tipo de máquina se llama
máquina de Moore en honor a E. F. Moore, quien la definió en 1956.
Muchos tipos de maquina incluyendo algunos componentes de ordenadores
pueden ser modelados utilizando una estructura llamada maquina de estado
finito. Varios tipos de maquina de estado finito incluyen un conjunto finito
de estado. Todas las versiones de maquinas de estado finito incluyen un
conjunto finito de estado, uno de los cuales es el estado y dato de entrada el
siguiente estado. Las maquinas de estado finito se utilizan con mucha
frecuencia en aplicaciones de ciencias de la computación y en redes de
datos.
Una maquina de estado finito con salida M = (S, I, O, f, g, s0) consiste en
un conjunto finito de estados S, un alfabeto (conjunto finito no vacío) de
entradas I, un alfabeto de salida O, un estado inicial s0, una función de
transición f: S x I → S y una función de salida g : S x I→ O.
Utilización:
Son la base de correctores ortográficos y gramaticales de de los
programas de indexación o de búsqueda de largas secuencias de
texto.
Para programas en el reconocimiento de voz de los programas que
transforman el texto utilizando lenguajes de mercado como XML y
HTML.
5
Ejemplos
6
Tipos de Maquina de Estado Finito
Se han desarrollado muchos tipos de maquinas de estado finito para
modelar las calculadoras. En esta sección hemos dado una definición de un
tipo de maquina de estado finito. En el tipo de maquina introducido en esta
sección las salidas corresponden a transiciones entre estado. Las maquinas
de este tipo se llaman máquinas de Mealy porque fue G.H. Mealy, en 1955,
el primero que las estudio.
Hay otro tipo importante de maquina de estado finito con salida, donde la
salida esta determinada solo por el estado.
Este tipo de maquina se llama maquina de Moore en honor a E.F.Moore
quien la introdujo en 1956. Las máquinas de Moore se consideran en una
serie de problemas al final de la sección.
Máquinas de Estado Finito Sin Salida
Definición : A diferencia de los Autómatas Finitos Deterministas, donde
existe una ´única forma de llegar de un estado a Otro con una entrada y se
tiene solo un estado inicial, los Autómatas Finitos No Deterministas no
cuentan con estas virtudes, pero son una herramienta de Mucha ayuda
cuando queremos diseñar un Autómata Determinista. Para cada Autómata
No Determinista existe un Autómata Determinista que lo representa y que
acepta el mismo lenguaje. Podemos definir un Autómata Finito No
Determinista como: A = {Q, I, F,}
Dónde:
Q: Conjunto finito de estados.
I: Conjunto de estados iniciales donde I ∈ Q.
F: Conjunto de estados finales F ⊆ Q.
7
Las máquinas de estado finito sin salida también llamadas autómatas de
estado finito, tienen un conjunto final de estados y reconocen una cadena
si, y solo si, lleva el estado inicial a un estado final.
Es otro tipo de máquina de estado finito que está especialmente diseñado
para el reconocimiento de leguajes. En lugar de producir una salida, estas
máquinas tiene estados finales. Una cadena es reconocida por la maquina
si, y solo si, se produce una transición del estado inicial a uno de estos
estados finales.
Es un sistema que acepta una entrada, que podía producir una salida y que
tiene un tipo de memoria interna que puede llevar registro de cierta
información acerca de las entradas anteriores. La condición interna
completa de la máquina y de toda su memoria, en un instante particular,
constituye el estado de la maquina en ese instante.
Ejemplos
8
Ventajas de las Maquinas de Estado Finito
Son intuitivas y fáciles de entender.
Abstraen convenientemente detalles secundarios que no son necesarios
para el análisis del sistema a un alto nivel y se centran en aspectos
claves del mismo.
Son universalmente aplicables.
Su uso es común unos sistemas de transmisión de datos y el uso de
protocolos de comunicación.
En programación minimiza grandemente la tendencia a escribir “código
espagueti” y puede ayudar a reducir de variable global necesaria,
aumentando al mismo tiempo la confiabilidad.
9
Conjunto de Cadena
Definición :
Un conjunto de cadena en maquitas este es reconocido como un programa
de diseño o un programa de coordenadas en las cuales logra reconocer o
por datos matemáticos las funciones de cada máquina si este son sin salida
o con salidas autómatas.
Antes de concentrarnos en la máquina de estado finito sin salida,
introduciremos algunos conceptos básicos relativos a conjuntos de cadenas,
Las operaciones que definiremos se usaran frecuentemente en el
reconocimiento de lenguajes mediante máquina de estado finito.
Ejemplo
10
