Afnd A Afd

Vol. (6) 1: pp. 61-70

CONVERSIÓN
DE UNA N AUN A D
F
F
()
1

()
2

E g rR i L
da uz .
E u r oR f oL
dad af .

AUTÓMATAS FINITOS(*)
RESUMEN
El artículo presenta la conversión
de un autómata finito no
determinista (AFN) a un autómata
finito determinista (AFD), haciendo
uso de la construcción por
subconjuntos. El algoritmo de
construcción por subconjuntos se
basa en laclausura transitiva o
cerradura ? , la implementación se
realiza mediante un programa en
lenguaje C++ , cuyo código y
salida se presentan en su totalidad.
Palabras Claves: Autómata finito
no determinista. Autómata finito
determinista. Grafo de
transiciones. Construcción de
subconjuntos.

ABSTRACT
This article presents the change
from a non-determinist fnite
automaton (AFN) into adeterminist
finite automaton (AFD), making use
of a subset construction. The
subset construction algorithm is
based on the transitive closure or
??
lock. Its implementation is done
through a C++ language program,
whose code and output are
thoroughly presented.
Key Words: Non-Determinist
Finite Automaton. Determinist Finite
Automaton. Transition graph.
Subset construction.

agosto 2003Un reconocedor de un lenguaje es un programa que toma como entrada una cadena “x y”,
responde "si" si x es una frase del programa, y "no", si no lo es. Se compila una expresión regular
en un reconocedor construyendo un diagrama de transiciones generalizado llamado autómata finito.
Un autómata finito puede ser determinista o no determinista, donde "no determinista" significa que en
un estado sepuede dar el caso de tener mas de una transición para el mismo símbolo de entrada.
Autómatas finitos no deterministas
Un autómata finito no determinista (abreviado, AFN) es un modelo formado por:
1.
2.
3.
4.
5.

Un conjunto de estados denotados como: estados S.
Un conjunto de símbolos de entrada S (el alfabeto símbolos de entrada).
Una función de transición mover que transforma paresestado-símbolo en conjuntos de estados.
Un estado S0 que se considera el estado de inicio (o inicial).
Un conjunto de estados F considerados como estados de aceptación (o finales).

Un AFN se puede representar mediante un grafo dirigido etiquetado, llamado grafo de transiciones,
en el que los nodos son los estados y las aristas etiquetadas representan las funciones de transición.
Este grafo separece a un diagrama de transiciones, pero el mismo carácter puede etiquetar dos o
más transiciones fuera de un estado, y las aristas pueden etiquetarse con el símbolo especial ? ?y
con símbolos de entrada.
En la Figura 1, se muestra el grafo de transiciones de un AFN que reconoce al lenguaje (a|b)*abb.
El conjunto de estados del AFN es {0,1,2,3} y el alfabeto de símbolos de entrada es {a,b}. El estado
0 de la figura 1 se considera el estado de inicio, y el estado de aceptación 3 está indicado mediante
un círculo doble.
Cuando se describe un AFN, se utiliza la representación de grafo de transiciones. En un computador,
puede aplicarse la función de transición de un AFN de varias formas. La implantación más sencilla es
una tabla de transiciones en donde hay una fila por cadaestado y una columna por cada símbolo de
entrada y ? , si es necesario.
(1)

(2)

(*)

D c n ed lD p r a e t d I g n e í d S s e a eI f r á i a
oet e eatmno e neira e itms nomtc.
F c l a d I g n e í I d s r a ,U M M
autd e neira nutil NS
E m i :e u z @ n s . d . e
-al rilummeup
D c n ed lD p r a e t d I g n e í d S s e a eI f r á i a
oet e eatmno e neira e itms nomtc.
F c l a d I g n eí I d s r a ,U M M
autd e neira nutil NS
E m i :e a f l u m m e u p
-al rfo@ns.d.e
L sf n a e t st ó i o h ns d t m d sd l p i e ar f r n i m n i n d e l b b i g a í . E p o r m e l n u j
o udmno ercs a io oao e a rmr eeeca ecoaa n a ilorfa l rgaa n egae
C +p e e t l i p e e t c ó d d c o a g r t o .
+ rsna a mlmnain e ihs loims

INGENIERÍA DE S ISTEMAS E INFORMÁTICA

61

>>>...