14:17

00

Temas  Definición de autómata finito  Autómata finito determinístico y no determinístico  Autómata finito de estados mínimos

Objetivo Que el estudiante logre: 1) Identificar conceptos constructivos de la Teoría de la autómatas. 2) Definir autómatas finitos. 3) Aplicar los algoritmos para convertir AFND a AFD y para obtener un AFD de estados mínimos.

14:17

11

Autómata • Dispositivo mecánico capaz de procesar cadenas de símbolos. • Dado un lenguaje L definido sobre un alfabeto A y una cadena x arbitraria, determina si x  L o x  L. • Un autómata tiene dos posibles reacciones: SI

Las hileras son reconocidas o aceptadas

Cadena x

Autómata NO Las hileras son rechazadas por el autómata

Lenguaje 14:17

22

Las gramáticas proporcionan un método para generar cadenas de un lenguaje y para reconocer cadenas de un lenguaje se han descripto autómatas de varios tipos. GRAMÁTICAS

Gramáticas no restringidas

Gramáticas sensibles al contexto

14:17

LENGUAJES

AUTÓMATAS

Lenguajes Irrestrictos o recursivamente enumerables (Tipo 0)

Máquinas de Turing

Lenguajes sensibles al contexto (Tipo 1)

Autómatas ligados linealmente

Gramáticas libres de contexto

Lenguajes libres de contexto (Tipo 2)

Gramáticas regulares

Lenguajes regulares (Tipo 3)

Autómatas de pila

Autómatas finitos

33

 Un autómata finito (AF) es un modelo de computación muy restringido, sin embargo tiene una gran aplicación en reconocimiento de patrones.  Es un dispositivo abstracto que posee un número finito de estados. Un AF cuenta con una cinta de entrada, una cabeza lectora y una unidad de control (puede estar en un estado en un instante dado).

14:17

44

Un AF es una quíntupla A =(Q, , , q0, F) Q es un conjunto finito y no vacío de estados  es un alfabeto finito (símbolos de entrada)  es una función de transición : Q x   Q q0 Q es el símbolo de inicio F Q es el conjunto de estados finales 14:17

55

Diagrama de transición • Un estado

• Estado de inicio • Estado de aceptación • Una transición EJEMPLO

a

A = ({q0 , q1), {a, b},  , q0 , {q0 ,q1}) con: (q0 ,a) = q0 (q0 , b) = q1 (q1 ,b) = q1 a q0

14:17

b

b q1

L(A) = {anbm / n,m ≥ 0}

66

Tabla de transición En cada fila se coloca un estado y se usan las columnas para los símbolos de entrada. En la intersección de fila y columna se coloca el conjunto de estados que pueden ser alcanzados por una transición del estado con la entrada. A veces, se utiliza un vector auxiliar cuyos elementos son los distintos estados finales. Tabla de Transición

EJEMPLO

A = ({q0 , q1), {a, b},  , q0 , {q0 ,q1}) con: (q0 ,a) = q0 (q0 , b) = q1 (q1 ,b) = q1 a q0

b

b

b

q0

q0

q1

q1

---

q1

Estados Finales

q1

L(A) = 14:17

a

{anbm

/ n,m ≥ 0}

q0 q1 77

 La transición directa  define transiciones de estados debido al procesamiento de un símbolo de entrada, por ejemplo, (q0 ,a) = q1 .  La función de transición  se puede extender a e que define transiciones de estados (múltiples) debido al procesamiento de una hilera de símbolos de entrada. Caso base: (q,)=q Inducción: e(q,xa)= (e(q,x),a) La función de transición extendida es una proyección: e : Q x *  Q Ejemplo a q0

14:17

b

b q1

e (q0,abb)= (e (q0,ab),b)=  (((q0,a),b),b)= ( (q0,b),b)=(q1,b)= q1

88





Un autómata finito A =(Q,,,q0,F) acepta una hilera x* si A, lee todos los símbolos de x, comenzando en el estado q0, leyendo primero el símbolo de la izquierda hasta que se pare en un estado final. Un lenguaje reconocido por un autómata se define:

L(A)=  x  * / e(q0,x)  F

Los lenguajes aceptados por AF son los regulares.

14:17

99

AF determinístico (AFD): si para todo (q,a)  Q x , |(q,a)| ≤ 1. Un AFD tiene a lo sumo una transición desde cada estado. AF No determinístico (AFND): conjunto de estados finales F  Q estado inicial, q0  Q A = (Q, , , q0, F) función de transición : Q   2Q alfabeto conjunto de estados Extensión de  a cadenas (: Q *  2Q )

Es decir, una proyección de parejas (estado, símbolo de entrada) a subconjuntos de Q en vez de a elementos individuales de Q. |(q,a)| > 1. Más de una función de transición para el símbolo a desde el estado q. 10 14:17 10

L = {xyz / x,z{0,1}*, y{00,11}} ER= (0/1)* (00/11) (0/1)* A = ({q0 , q1 , q2, q3), {0,1},  , q0 , {q2}) con: 0,1

q0

0,1

0

q1

0

q2 1

1 q3

(q0 ,0) = {q0, q1} (q0 , 1) = {q0, q3} (q1 ,0) = {q2} (q1 ,1) =  (q2, 0) = {q2} (q2,1) = {q2 }

(q3,0) =  (q3, 1) = {q2 }

En los Autómatas Finitos, todo se puede resolver con un Autómata Finito Determinístico. TEOREMA: Sea L un lenguaje aceptado por un AFND. Entonces existe un AFD que acepta el mismo lenguaje L. L(AFND) = L(AFD). 11 14:17 11

PROCEDIMIENTO DE CONVERSIÓN DE AFND A AFD: 1) Se especifican las funciones de transición. 2) Si (q0 ,a) = q0 ,q1 ,…,qn  '(q0 ,a) = q01 ... n , con ’ A' 3) Se obtienen las funciones de transición para los nuevos estados donde: '(q01 ... n ,a) = (q0 ,a)  (q1 ,a) ...  (qn ,a) 4) Se determina el conjunto F' de estados finales q01 ... n  F'  q0  F  q1  F  ...  qn  F con F y F' conjunto de estados finales de A y A' . A = ({q0 ,q1 ,q2}, {a,b},  ,q0, {q2}) a

q0

b

a b

q1

b

q2

(q0 ,a) = {q0, q1}  '(q0 ,a) = q01 (q1 ,b) = {q0, q1, q2} '(q1 ,b)= q012 (q0 ,b) = (q1,a) = (q2 ,a) = (q2 ,b) =  A = ({q0 ,q01 ,q012}, {a,b},  , q0, {q012})

Se obtienen las funciones de transición para los nuevos estados: '(q01,a) = (q0 ,a)  (q1 ,a) = q01= q01 '(q01,b) = (q0,b)  (q1,b) =   q012 = q012 '(q012,a) = (q0,a)  (q1,a)  (q2,a) = q01    = q01 '(q012 ,b) = (q0 ,b)  (q1 ,b)  (q2,b) =   q012   =q012 14:17

a

q0

a

q01

b

b a

q012

12 12

Procedimiento para encontrar un AFD de estados mínimos: 1) Se crea un estado trampa para aquellas funciones de transición no definidas. Las funciones de transición del estado trampa también se definen. 2) Se construye una matriz triangular superior. Se marca con una X los estados no equivalentes. Inicialmente se marcan las entradas correspondientes a un estado final y a un estado no final, que son no equivalentes. 3) Para cada par de estados p y q aún no marcados se prueba si por transitividad son también no equivalentes. Para cada símbolo de entrada a, se consideran los pares de estados: r = (p,a) s = (q,a) Si la entrada (r,s) en la tabla tiene una X también se coloca una X en la entrada (p,q). Si la entrada (r,s) no está aún marcada entonces el par (p,q) se ubica en la lista de espera. Más adelante, si (r,s) recibe una X entonces cada par en la lista de espera asociada con (r,s) también recibe una X. 4) Todos los estados no marcados son equivalentes. Se construye el autómata finito determinístico de estados mínimos equivalente al dado. 14:17

13 13

A = ({1,2,3,4,5,}, {a,b}, , 1, {2,3,5}) (1,a) = 1 (1,b) = 2 (2,a) = 4 (2,b) = 3 (3,a) = 4

(3,b) = 3 (4,a) = 5 (4,b) =  (5,a) =  (5,b) = 5

(4,b) = T (5,a) = T (T,a) = T (T,b) = T a

a

1

1) Se crea un estado trampa para las transiciones no especificadas:

b b

2

b

2

b

3 a

a

a/b T

4

b

a 4 a

a

a

5

b

1

3 a

14:17

b

b

5

b

14 14

2) Se construye la matriz triangular superior y se marcan los estados no equivalentes.

a

b b

1

2

a/b

b

3

a

a

b

T

4 a

a 5

1 2 3 4 5

14:17

2

3

X

X

4

b

5

T

X X X

X X X X 15 15

3) Para cada par de estados p y q aún no marcados se prueba si por transitividad son también no equivalentes. a

1

2

3

4

5

T

X

X

X X X

X X X X

X X X X X

2 3 4 5

Son equivalentes

Se intenta marcar (1,4) (1,a) = 1 (1,5) con X Se marca (1,4) (4,a) = 5

Se intenta marcar (1,T) (1,a) = 1 (1,b) = 2 (T,a) = T (T,b) = T

14:17

b

1

2

a/b T

b a b

3 a 4 a

a 5

Se intenta marcar (2,5) (2,a) = 4 (2,b) = 3 (5,a) = T (5,b) = 5

(2,T) con X

Se intenta marcar (2,3) (2,a) = 4 (2,b) = 3 (3,a) = 4 (3,b) = 3

b

Se marca (1,T)

b

Lista de espera

Se intenta marcar (4,T) (4,a) = 5 (5,T) con X Se marcan (T,a) = T (4,T), (2,5) Se intenta marcar (3,5) (3,a) = 4 (3,b) = 3 (5,a) = T (5,b) = 5

16 16

Los estados 2 y 3 que no están marcados significan que son equivalentes. Autómata inicial a

b b

1

2

a/b T

b a b

3 a

a

a

1

b

b

4

a

5

14:17

Autómata de Estados Mínimos

b

23

a

4

a

5

b

17 17

Permiten realizar cálculos a partir de una cadena de entrada, o sea, traducen una cadena de entrada en una cadena de salida. x

Autómata Finito Traductor

x’

Lenguaje Regular Un AFD es una 7-upla A =(Q, , , q0, F,O,)

 Q, , , q0, F coinciden con la definición de autómatas finitos.  O es un conjunto finito de símbolos de salida.   es la función (posiblemente parcial) de salida : Q x   O* En la representación gráfica de un traductor finito, el valor de  se agrega como un nuevo rótulo sobre los arcos. Sea (q, a) = q' y (q, a) = y  O*; entonces a || y rotulan el arco que conecta q y q'. 18 14:17 18

Función de traducción para cadenas

La extensión natural de , * : Q x *  O* se define: *(q, ) =  *(q, xa) = *(q, x). ( e* (q, x), a)  La diferencia entre  y * es que  se define desde un estado y un símbolo del alfabeto, y * se define desde un estado y una cadena de símbolos. EJEMPLO: Autómata finito traductor que calcula f(x) = 2x + 3 para x  N, x > 0, x representado en unario. x=1 traduce 11111 x=2 traduce1111111

q0

14:17

1|| 11111

1||11

A = ({q0 , q1), {1},  , q0 , {q1}, {1}, ) con:

q1

(q0 ,1) = q1

(q1 ,1) = q1 (q0 ,1)=11111 (q1 ,1)=11 19 19

Autómata Finito

Autómata Finito Determinístico

Alg. para convertir

Autómata Finito No Determinístico

Autómata Finito de Estados Mínimos

Métodos Autómata Finito

Expresiones Regulares

Gramáticas Regulares Importancia Práctica: se usan para los Analizadores Léxicos. 14:17

20 20