Autómatas Finitos No Deterministas
Autómatas Finitos No Deterministas
Autómatas Finitos No Deterministas
Computación
Ingeniería de Sistemas de Información
Clase Nº 2 de AFN
Temas a tratar
Definición formal de un Autómata Finito
Determinismo:
Máquina del AF:
Definición formal de Computación para un AF
Definición formal de un AF
Conjunto finito de estados,
Alfabeto de entrada,
Función de transición,
Estado inicial, y
Conjunto de estados de aceptación.
Determinismo
Todos los estados tienen una transición por cada uno de los símbolos del alfabeto.
En los diagramas de estado no representamos todas las transiciones porque no todas
nos interesan.
Máquina del AF
Reconoce un lenguaje
Acepta o rechaza cadenas de símbolos.
Las cadenas están compuestas exclusivamente por los símbolos del alfabeto.
Las cadenas pertenecen a un cierto lenguaje.
Ejemplos de AF’s.
Operaciones regulares.
Definición formal de
computación para un AF
Formalizaremos la computación (cómo computa, cómo procesa) de una cadena de
símbolos de entrada un AF.
Es importante que pensemos, -en forma paralela- que un AF es una máquina que, si
bien es abstracta- no por ello deja de tener mecanismos específicos de
funcionamiento que ahora detallaremos.
Como ayuda, pensemos que un AF como en la siguiente figura:
Autómata finito como máquina
Alfabeto:
Lenguaje
0, 1
ESTADOS
ACEPTA RECHAZA
RECHAZA
Cadena de entrada
Definición de Computación en un AF
Sea
M reconoce el lenguaje A si .
Definición 1.23
Sean A y B lenguajes, entonces definimos:
Unión: (verlo con diagramas de Venn)
Concatenación: }
Estrella:
MUY IMPORTANTE: la cadena vacía SIEMPRE será miembro de A*, sin importar
cómo sea A.
Operaciones regulares.
Clausuras
Teorema 1.25:
La clase de los lenguajes regulares está clausurada respecto de la operación unión.
Teorema 1.26:
La clase de los lenguajes regulares está clausurada respecto de la operación concatenación.
Tenemos un problema aquí: ¿cómo sabe la máquina dónde termina la parte de la cadena de
entrada que corresponde al lenguaje A, o -de otra forma- dónde comienza la parte de la
cadena de símbolos de entrada que corresponde al lenguaje B?
Para resolver este problema, introduciremos la técnica denominada no determinismo.
Definiremos así el Teorema 1.47.
¿qué pasa con la operación estrella? Veremos este tema más adelante con el Teorema
1.49.
No Determinismo
Computación no determinista
No Determinismo
Una máquina determinista tiene un único camino computacional. Sabemos exactamente a qué
estado pasará cuando estamos en un cierto estado y se lee un determinado símbolo en la
entrada.
El no determinismo funciona de otra manera. Si la máquina está en un estado específico y se lee
un cierto símbolo en la entrada, la computación puede ramificarse de tal modo que continúe
en varios estados en forma simultánea. Es una computación en paralelo. También es usual que
un cierto estado no tenga transiciones para todos los símbolos del alfabeto de entrada. Y
además, aparecen las denominadas transiciones instantáneas o transiciones vacías, esto es,
aquellas que no necesitan de ningún símbolo (o sea, la cadena vacía) para llevar la máquina de
un estado a otro.
En realidad, el no determinismo es una generalización del determinismo al punto que, -como
veremos más adelante- todo autómata no determinista tiene su equivalente determinista.
Entonces, ¿cuáles son las ventajas del no determinismo sobre el determinismo? Estos autómatas,
¿son más poderosos?, ¿reconocen más lenguajes que los deterministas? ¿Cómo aceptan o rechazan
las cadenas leídas estos autómatas?
Veremos algunos ejemplos para comprender mejor el concepto…
Definición formal de un Autómata
Finito No Determinista
AFD y los AFN son muy similares:
Los
constan de una colección de estados
tienen un alfabeto de entrada
un estado inicial
un conjunto de estados de finalización/aceptación.
Ejemplo 1.38: la definición formal de N1 es (Q, , , q1 , F) donde:
1. Q = {q1, q2, q3, q4},
0 1 λ
2. ,
q1 {q1} {q1, q2} Ø
3. es dada por:
q2 {q3} Ø {q3}
4. q1 es el estado inicial, y q3 Ø {q4} Ø
5. . q4 {q4} {q4} Ø