AFND A AFD

INSTITUTO TECNOLOGICO DE MINATITLAN

NOMBRE DEL CATEDRATICO:

M.C. José Angel Toledo Alvarez

NOMBRE DELALUMNO:

Orozco Ayometzi Maribell

UNIDAD 3
Investigación
CONVERSION DE UN AFN A UN AFD

CARRERA:

Ing. Sistemas computacionales
SEMESTRE:

Quinto

Minatitlan, Ver a 25 de marzo del 2004
AUTÓMATAS FINITOS DETERMINISTICOS
(AFD)
Una máquina de estado finito se utilizapara representar
expresiones regulares. Para entender su funcionamiento es
conveniente familiarizarnos con algunos conceptos de la simbología
formal y hacer la relación con un grafo. Una máquina de estados
finitos es un quíntuplo en el cual se señalan el alfabeto y la función de
traslación entre estados. La transición es única, ya que de cada
estado salen exactamente el número de elementos delalfabeto.
Estos autómatas no tienen almacenamiento temporal. Debido a
que el número de estados es finito, un AFD puede tratar únicamente
con situaciones en las cuales la información a ser almacenada en
determinado tiempo está estrictamente limitada. Para representar
estos autómatas, usamos grafos de transición, en los cuales los
vértices representan los estados y las ligas las transiciones.Un
lenguaje es el conjunto de cadenas aceptadas por un Autómata.
Se requiere mostrar la teoría de grafos, a manera de
recordatorio, ya que éste es un tema de la asignatura de Matemáticas
Discretas.
Es una herramienta útil para generar palabras pertenecientes
a un lenguaje determinado son las expresiones regulares. Ahora nos
gustaría tener otra herramienta, que dado un lenguaje y una ciertacadena, podamos determinar con certeza si ella pertenece o no al
lenguaje. La herramienta más básica que usaremos para ello son los
AFD, cuyo funcionamiento se basa en ir leyendo caracteres desde una
cinta que contiene caracteres en un alfabeto.

2

Cada vez que la maquina lee un caracter desde la cinta, cambia
a un estado nuevo que depende del estado anterior. Si al leer el
ultimocaracter de la cinta, el autómata quedó en un estado
perteneciente al conjunto de estados finales, entonces la cadena
pertenece al lenguaje asociado al autómata. (la definición formal ya
fué vista en clases).
Al hablar sobre el lenguaje asociado a un autómata, estamos
intuitivamente afirmando que todos los autómatas tienen un lenguaje
asociado. Esto es cierto, y para cada expresión regularpodremos
encontrar un autómata que reconozca todas las palabras que la
expresión genera y viceversa.
Sin embargo, un Lenguaje no está asociado a un único
autómata. Es más, a un mismo lenguaje le podemos asociar siempre
muchos autómatas que reconocen las cadenas en él.
El recíproco sin embargo no es cierto: un autómata reconoce
uno y solo un lenguaje.
Aceptación de una palabra
Cuando rastreamosel AFD, nos damos cuenta que la cantidad
de caminos desde un estado se reduce al número de elementos del
alfabeto. Por lo tanto hay que concentrarnos en las configuraciones
convenientes para armar un buen autómata. Muchas veces hacemos
autómatas redundantes, y aunque aceptan las palabras requeridas,
no son óptimos y eso se manifiesta en la implementación del AFD por
computadora.
Unamáquina de estados finitos
donde

es un quíntuplo (K, Σ , δ ,s, F ),

K es un conjunto de identificadores de estados
Σ es el alfabeto de entrada
s ∈ K es el estado inicial
F ⊆ K es un conjunto de estados finales
δ : KxΣ → K es la función de transición
Una configuración es la situación en que se encuentra la máquina en
un momento dado.
Definición. [q1,w1] M [q2,w2] ssi w1=σ w2 para un σ ∈ Σ ,y existe
una transición en M tal que
δ (q1, σ )=q2

3

Definición. Una palabra w ∈ Σ * es aceptada por una máquina M=(K,
Σ , δ ,s, F ) ssi existe un estado
q ∈ F tal que [s,w] M* [q, ε ]
Definición. Un cálculo en una máquina M es una secuencia de
configuraciones c1,c2,...,cn tales que ci  ci+1.
Teorema. Dados una palabra w ∈ Σ * y una máquina M, sólo hay un
cálculo
[s,w] M......