Autómatas Finitos No Deterministas

Descargar como pptx, pdf o txt
Descargar como pptx, pdf o txt
Está en la página 1de 18

Teoría de la

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

qq00 qq11 qq22 …… qqii …. qqnn


01010101010110

ACEPTA RECHAZA
RECHAZA
Cadena de entrada
Definición de Computación en un AF
  Sea

 Sea una cadena en donde cada es un miembro del alfabeto .


 M acepta a w si existe una secuencia de estados en Q y se cumplen estas
tres condiciones:
1. ,
2. , y
3.

 M reconoce el lenguaje A si .

 Denominamos LENGUAJE REGULAR a aquel lenguaje que es aceptado por un


AF.
Diseño de AF’s
 Método “yo soy el autómata”.
 No es necesario memorizar cada símbolo que leemos.
 Un autómata finito (es decir, con una cantidad finita de estados) puede procesar
cadenas de gran cantidad de símbolos. De hecho puede procesar una cadena
infinita.
 Recordar que la decisión de aceptar o rechazar SÓLO puede tomarse al finalizar de
leer la cadena de símbolos de entrada. No antes.
Ejemplos de AF’s

 Hacer los ejemplos del apunte…


Operaciones
Regulares
Propiedades de los autómatas finitos y de los lenguajes regulares
Operaciones Regulares
  UNIÓN
 CONCATENACIÓN
 OPERACIÓN ESTRELLA.

 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

 una función de transición

 un estado inicial
 un conjunto de estados de finalización/aceptación.

¿dónde está la diferencia? En la función de transición.


Mientras que en un AFD la función de transición toma un estado y un símbolo leído para pasar a un nuevo
estado, en un AFN la función de transición toma un estado y un símbolo de entrada ó la cadena vacía y produce
un conjunto de estados siguientes posibles.
Para entender mejor esto necesitamos unos conceptos y notación adicionales: el concepto de conjunto
potencia y saber que para cualquier alfabeto , podemos escribir que es .
Ahora podemos escribir la función de transición de un AFN como
Definición formal de un Autómata
Finito No Determinista

   AFN es una 5-tupla (Q, , , q , F) en donde:


Un 0

 Q es un conjunto finito de estados,


 es un alfabeto finito,
 es la función de transición,
 es el estado inicial, y
 es el conjunto de estados de aceptación.
Definición formal de un Autómata Finito No Determinista

 
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} Ø

También podría gustarte