Maquinas de estado Finito

M´quinas de Estados Finitos
a
Breve Introducci´n
o
Jorge Alejandro Guti´rrez Orozco
e
Escuela Superior de C´mputo
o
22 de agosto de 2008
Resumen
Hablaremos de algunas de las m´s comunes M´quinas de Estados Fina
a
tos, una breve descripci´n sobre ellas, su definici´n formal y sus relacioo
o
nes entre ellas. En la ultima secci´n se da una sencilla definici´n de una
´
o
o
M´quina deTuring. Existen varios temas que se deben de conocer antes de
a
abordar M´quina de Turing, pero dado que la explicaci´n que se propone
a
o
no es del todo profunda, no es necesario tener amplias bases te´ricas. El
o
presente va dirigido a alumnos de Nivel Superior como material de apoyo
en el estudio de M´quinas de estados finitos. Se ofrece un enfoque diferente
a
con explicacionessumamente sencillas.

1

Se necesitan conocimientos previos antes abordar los siguientes temas, as´ que
ı
explicaremos brevemente algunos conceptos que utilizaremos.
Conjunto : Es un colecci´n de objetos relacionados entre ellos. Un conjunto
o
solo indica los elementos que lo componen, por tanto no es necesario tener
un orden y no se repiten los elementos dentro de un conjunto. Un Conjuntofinito es aquel donde podemos contar sus elemntos, por ejemplo:
C = {♥, ♣, ♦, ♠} claramente podemos notar que son cuatro elementos.
En un Conjunto infinito encontramos de dos tipos: los Conjuntos Infinitos no Numerables donde no podemos contar todos los elementos, un buen
ejemplo es el conjunto de todos los n´ meros reales ℜ y el conjunto de los
u
Infiniftos Numerables como el caso de los n´ merosnaturales N, donde
u
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
o
conjunto de igual o mayor n´ mero de miembros. Por ejemplo: consideu
remos 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
u
el conjunto Apudiese llegar a tener los mismos elementos que B pero sin
dejar de ser subconjunto se deber´ escribir A ⊆ B . Dos conjuntos con los
a
mismos elementos son iguales.
S´mbolo : Es la representaci´n abstracta de un objeto, puede ser un d´
ı
o
ıgito
o una letra. En general es cualquier caracter que nos represente alg´ n
u
elemento. Algunos ejemplos son: a, 1, π , etc.
Alfabeto : Tambi´nllamado Vocabulario, es un conjunto finito de s´
e
ımbolos. Debe existir al menos un s´
ımbolo en el alfabeto, es decir el alfabeto
no puede ser un conjunto vac´ Comunmente se le denomina Σ a este
ıo.
conjunto.
Cadena : Es una secuencia de s´
ımbolos hecha con los elementos de un
Alfabeto, por eso se dice que una cadena ω sobre un alfabeto Σ es un
elemento del alfabeto universal Σ∗ , esdecir ω ∈ Σ∗ , donde Σ∗ es un
conjunto formado de todas las posibles cadenas que se puedan hacer con los
elementos de Σ. Una cadena no es un subconjunto del Alfabeto universal,
es alguno de sus elementos. Una cadena no puede ser infinita. Tambi´n
e
se le conoce como frase o palabra. Por ejemplo consideremos un alfabeto
Σ = {1, 0}, entonces Σ∗ = {1, 0, 00, 01, 10, 11, 000, ...} una cadena ω sobreΣ podr´ ser 101011010, esta cadena es un elemento de Σ∗ .
ıa
Lenguaje : Es un conjunto de cadenas, las cuales deben estar formadas
con los s´
ımbolos de un Alfabeto Σ, entonces decimos que el Lenguaje L
est´ sobre el Alfabeto Σ. Por ejemplo: el lenguaje L = {100, 001, 00, 1111}
a
se forma con los elemetos de Σ = {1, 0}, la cadena σ = 1010 se forma
tambi´n con los elemntos de Σ (i.e. σ ∈Σ) pero no pertenece al lenguaje
e
L y se denota σ ∈ L.
/
Estado : Es la situaci´n o las condiciones en que se halla un objeto en
o
alg´ n momento, dicho objeto no puede estar en m´s de un estado al mismo
u
a
tiempo. En el caso de una m´quina son las caracter´
a
ısticas que posee en un
momento dado.
2

Algoritmo : Es una secuencia finita de instrucciones bien definidas. Un...