Maquinas estado finito

Universidad
Facultad
Escuela
Semestre
Asignatura
Profesor
Tema
Alumno
Lugar - Fecha

UNAC - Universidad Nacional del Callao
FIIS - Facultad de Ingeniería Industrial y de Sistemas
EPIS - Escuela Profesional de Ingeniería de Sistemas
2010-V
Ingeniería de Sistemas
Lic. Guillermo A. Mas Azahuanche
Máquinas de Estado Finito
Trucíos Chacón, José M. – 085022E
Callao, domingo 28 defebrero del 2010

NOAM CHOMSKY

"Si asumes que no hay esperanza, garantizas que no habrá esperanza.
Si asumes que hay un instinto hacia la libertad, que hay oportunidad para
cambiar las cosas, entonces hay una opción de que puedas contribuir a
hacer un mundo mejor.
Esta es tu alternativa."

2

ÍNDICE
tema
Introducción
Definiciones previas
- Conjunto
- Subconjunto
- Símbolo
-Alfabeto
- Cadena
- Lenguaje
- Estado
- Algoritmo
- Computación
- Modelo científico
- Modelo matemático
Autómatas Finitos
- Autómatas
- Autómatas Finitos
- Autómatas Finitos: Descripción simple
- Autómatas Finitos: Importancia y ejemplos
- Autómatas Finitos: Ventajas y desventajas
Clasificación de Autómatas Finitos
- Autómata Finito Determinista
- Autómata Finito No DeterministaMáquinas de Estados Finitos Transductoras / Aceptadoras
- Máquina de Moore
- Máquina de Mealy
Máquina de Turing
Jerarquía de Chomsky
- Jerarquía de Chomsky en Autómatas Finitos
Ejercicios
Bibliografía
Anexos
- Alan Turing
- Prueba de Turing
- Noam Chomsky

página
3
5

7

11

13

16
18
20
26
27

3

INTRODUCCIÓN

Las “Máquinas de Estados Finitos” (en inglés “Finite StateMachines”), nos
sirven para realizar procesos bien definidos en un tiempo discreto.
Reciben una entrada, hacen un proceso y nos entregan una salida.
Notemos que estas máquinas hacen una computación.
En otras palabras, imaginemos una máquina capaz de seguir una
secuencia finita de pasos al introducir un conjunto de datos en ella, solo se
puede leer un dato en cada paso que se realice, portanto el número de
pasos a seguir está dado por el número de datos a introducir. Cada
entrada diferente genera una salida diferente, pero siempre el mismo
resultado con los mismos datos de entrada.
Por lo tanto una computación es capaz de resolver un problema, si y solo
si tiene una solución algorítmica, es decir, puede ser descrito mediante
una secuencia finita de pasos bien definidos.Mediante una computación podemos encontrar soluciones a problemas
que teóricamente tienen una representación algorítmica, pero que
pueden necesitar tal cantidad de recursos (factores como el tiempo y el
espacio de almacenamiento) que desde el punto de vista práctico no se
puede llegar a la solución.

4

DEFINICIONES PREVIAS
Conjunto
Es una colección de objetos relacionados entre ellos. Unconjunto solo indica los
elementos que lo componen, por tanto no es necesario que tengan un orden y no se
repiten los elementos dentro de un conjunto.
Un “conjunto finito” es aquel donde podemos contar sus elementos, por ejemplo C =
{♥,♣,♦,♠}; en donde claramente podemos notar que son cuatro elementos.
Los “conjuntos infinitos” los encontramos de dos tipos: los “conjuntos infinitos nonumerables” donde no podemos contar todos los elementos, un buen ejemplo es el
conjunto de todos los números reales ℜ y el conjunto de los “infinitos numerables”
como el caso de los números naturales N, donde podemos numerar todos los
elementos aunque haya un infinito de ellos.
Subconjunto
Es una colección de elementos que a su vez pertenece a otro conjunto de igual o
mayor número de miembros. Porejemplo: consideremos los conjuntos A = {a, b} y B =
{z, a, c, b, d} se dice que A es un subconjunto propio de B y se escribe como A ⊂ B, si
en algún momento el conjunto A pudiese llegar a tener los mismos elementos que B
pero sin dejar de ser subconjunto se debería escribir A ⊆ B. Dos conjuntos con los
mismos elementos son iguales.
Símbolo
Es la representación abstracta de un objeto, puede...