diapositiva 1 -...
TRANSCRIPT
![Page 1: Diapositiva 1 - ecaths1.s3.amazonaws.comecaths1.s3.amazonaws.com/programacion2/851793929.U3-Automatas... · Un autómata finito (AF) es un modelo de computación muy restringido,](https://reader031.vdocumento.com/reader031/viewer/2022021903/5ba2aff209d3f2a1708c4b3d/html5/thumbnails/1.jpg)
0 0 14:17
![Page 2: Diapositiva 1 - ecaths1.s3.amazonaws.comecaths1.s3.amazonaws.com/programacion2/851793929.U3-Automatas... · Un autómata finito (AF) es un modelo de computación muy restringido,](https://reader031.vdocumento.com/reader031/viewer/2022021903/5ba2aff209d3f2a1708c4b3d/html5/thumbnails/2.jpg)
1 1 14:17
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.
![Page 3: Diapositiva 1 - ecaths1.s3.amazonaws.comecaths1.s3.amazonaws.com/programacion2/851793929.U3-Automatas... · Un autómata finito (AF) es un modelo de computación muy restringido,](https://reader031.vdocumento.com/reader031/viewer/2022021903/5ba2aff209d3f2a1708c4b3d/html5/thumbnails/3.jpg)
2 2 14:17
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:
Autómata
Las hileras son
reconocidas o
aceptadas SI
Las hileras son
rechazadas por
el autómata
NO
Cadena x
Lenguaje
![Page 4: Diapositiva 1 - ecaths1.s3.amazonaws.comecaths1.s3.amazonaws.com/programacion2/851793929.U3-Automatas... · Un autómata finito (AF) es un modelo de computación muy restringido,](https://reader031.vdocumento.com/reader031/viewer/2022021903/5ba2aff209d3f2a1708c4b3d/html5/thumbnails/4.jpg)
3 3 14:17
Gramáticas no restringidas
Gramáticas sensibles al contexto
Gramáticas libres de contexto
Gramáticas regulares
Lenguajes Irrestrictos o recursivamente
enumerables (Tipo 0)
Lenguajes sensibles al contexto (Tipo 1)
Lenguajes libres de contexto (Tipo 2)
Lenguajes regulares (Tipo 3)
Máquinas de Turing
Autómatas ligados
linealmente
Autómatas de pila
Autómatas finitos
GRAMÁTICAS LENGUAJES AUTÓMATAS
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.
![Page 5: Diapositiva 1 - ecaths1.s3.amazonaws.comecaths1.s3.amazonaws.com/programacion2/851793929.U3-Automatas... · Un autómata finito (AF) es un modelo de computación muy restringido,](https://reader031.vdocumento.com/reader031/viewer/2022021903/5ba2aff209d3f2a1708c4b3d/html5/thumbnails/5.jpg)
4 4 14:17
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).
![Page 6: Diapositiva 1 - ecaths1.s3.amazonaws.comecaths1.s3.amazonaws.com/programacion2/851793929.U3-Automatas... · Un autómata finito (AF) es un modelo de computación muy restringido,](https://reader031.vdocumento.com/reader031/viewer/2022021903/5ba2aff209d3f2a1708c4b3d/html5/thumbnails/6.jpg)
5 5 14:17
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
![Page 7: Diapositiva 1 - ecaths1.s3.amazonaws.comecaths1.s3.amazonaws.com/programacion2/851793929.U3-Automatas... · Un autómata finito (AF) es un modelo de computación muy restringido,](https://reader031.vdocumento.com/reader031/viewer/2022021903/5ba2aff209d3f2a1708c4b3d/html5/thumbnails/7.jpg)
6 6 14:17
Diagrama de transición
• Un estado
• Estado de inicio
• Estado de aceptación
• Una transición a
A = ({q0 , q1), {a, b}, , q0 , {q0 ,q1}) con: (q0 ,a) = q0 (q0 , b) = q1 (q1 ,b) = q1
b L(A) = {anbm / n,m ≥ 0} a
q0
EJEMPLO
b
q1
![Page 8: Diapositiva 1 - ecaths1.s3.amazonaws.comecaths1.s3.amazonaws.com/programacion2/851793929.U3-Automatas... · Un autómata finito (AF) es un modelo de computación muy restringido,](https://reader031.vdocumento.com/reader031/viewer/2022021903/5ba2aff209d3f2a1708c4b3d/html5/thumbnails/8.jpg)
7 7 14:17
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.
L(A) = {anbm / n,m ≥ 0}
a b
q0 q0 q1
q1 --- q1
q0 q1
Estados Finales
Tabla de Transición
b a
q0
b
q1
A = ({q0 , q1), {a, b}, , q0 , {q0 ,q1}) con: (q0 ,a) = q0 (q0 , b) = q1 (q1 ,b) = q1
EJEMPLO
![Page 9: Diapositiva 1 - ecaths1.s3.amazonaws.comecaths1.s3.amazonaws.com/programacion2/851793929.U3-Automatas... · Un autómata finito (AF) es un modelo de computación muy restringido,](https://reader031.vdocumento.com/reader031/viewer/2022021903/5ba2aff209d3f2a1708c4b3d/html5/thumbnails/9.jpg)
8 8 14:17
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
e (q0,abb)= (e (q0,ab),b)= (((q0,a),b),b)=
( (q0,b),b)=(q1,b)= q1 b a
q0
b
q1
![Page 10: Diapositiva 1 - ecaths1.s3.amazonaws.comecaths1.s3.amazonaws.com/programacion2/851793929.U3-Automatas... · Un autómata finito (AF) es un modelo de computación muy restringido,](https://reader031.vdocumento.com/reader031/viewer/2022021903/5ba2aff209d3f2a1708c4b3d/html5/thumbnails/10.jpg)
9 9 14:17
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.
![Page 11: Diapositiva 1 - ecaths1.s3.amazonaws.comecaths1.s3.amazonaws.com/programacion2/851793929.U3-Automatas... · Un autómata finito (AF) es un modelo de computación muy restringido,](https://reader031.vdocumento.com/reader031/viewer/2022021903/5ba2aff209d3f2a1708c4b3d/html5/thumbnails/11.jpg)
10 10 14:17
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):
A = (Q, , , q0, F)
conjunto de estados
alfabeto
función de transición
: Q 2Q
estado inicial, q0 Q
conjunto de estados finales F Q
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.
![Page 12: Diapositiva 1 - ecaths1.s3.amazonaws.comecaths1.s3.amazonaws.com/programacion2/851793929.U3-Automatas... · Un autómata finito (AF) es un modelo de computación muy restringido,](https://reader031.vdocumento.com/reader031/viewer/2022021903/5ba2aff209d3f2a1708c4b3d/html5/thumbnails/12.jpg)
11 11 14:17
q1 q2
0,1
0 0
1
q0
0,1
q3
1
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:
(q0 ,0) = {q0, q1} (q3,0) =
(q0 , 1) = {q0, q3} (q3, 1) = {q2 }
(q1 ,0) = {q2}
(q1 ,1) =
(q2, 0) = {q2}
(q2,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).
![Page 13: Diapositiva 1 - ecaths1.s3.amazonaws.comecaths1.s3.amazonaws.com/programacion2/851793929.U3-Automatas... · Un autómata finito (AF) es un modelo de computación muy restringido,](https://reader031.vdocumento.com/reader031/viewer/2022021903/5ba2aff209d3f2a1708c4b3d/html5/thumbnails/13.jpg)
12 12 14:17
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}) (q0 ,a) = {q0, q1} '(q0 ,a) = q01
(q1 ,b) = {q0, q1, q2} '(q1 ,b)= q012
(q0 ,b) = (q1,a) = (q2 ,a) = (q2 ,b) =
b q0 q1 q2
b
a b
a
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 a q0 q01 q012
b
a b
a
A = ({q0 ,q01 ,q012}, {a,b}, , q0, {q012})
![Page 14: Diapositiva 1 - ecaths1.s3.amazonaws.comecaths1.s3.amazonaws.com/programacion2/851793929.U3-Automatas... · Un autómata finito (AF) es un modelo de computación muy restringido,](https://reader031.vdocumento.com/reader031/viewer/2022021903/5ba2aff209d3f2a1708c4b3d/html5/thumbnails/14.jpg)
13 13 14:17
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.
![Page 15: Diapositiva 1 - ecaths1.s3.amazonaws.comecaths1.s3.amazonaws.com/programacion2/851793929.U3-Automatas... · Un autómata finito (AF) es un modelo de computación muy restringido,](https://reader031.vdocumento.com/reader031/viewer/2022021903/5ba2aff209d3f2a1708c4b3d/html5/thumbnails/15.jpg)
14 14 14:17
A = ({1,2,3,4,5,}, {a,b}, , 1, {2,3,5})
(3,b) = 3
(4,a) = 5
(4,b) =
(5,a) =
(5,b) = 5
(1,a) = 1
(1,b) = 2
(2,a) = 4
(2,b) = 3
(3,a) = 4
a
1 2 3
b
b b
a
4
5 b
a
a
1) Se crea un estado trampa para
las transiciones no especificadas:
(4,b) = T
(5,a) = T
(T,a) = T
(T,b) = T
a
1 2 3
b
b b
a
4
5 b
a
a
T
a/b b
a
![Page 16: Diapositiva 1 - ecaths1.s3.amazonaws.comecaths1.s3.amazonaws.com/programacion2/851793929.U3-Automatas... · Un autómata finito (AF) es un modelo de computación muy restringido,](https://reader031.vdocumento.com/reader031/viewer/2022021903/5ba2aff209d3f2a1708c4b3d/html5/thumbnails/16.jpg)
15 15 14:17
2) Se construye la matriz triangular superior y se marcan los estados no equivalentes.
a
1 2 3
b
b b
a
4
5 b
a
a
T
a/b b
a
2 3 4 5 T
1 X X X 2 X X 3 X X 4 X 5 X
![Page 17: Diapositiva 1 - ecaths1.s3.amazonaws.comecaths1.s3.amazonaws.com/programacion2/851793929.U3-Automatas... · Un autómata finito (AF) es un modelo de computación muy restringido,](https://reader031.vdocumento.com/reader031/viewer/2022021903/5ba2aff209d3f2a1708c4b3d/html5/thumbnails/17.jpg)
16 16 14:17
3) Para cada par de estados p y q aún no marcados se prueba si por transitividad
son también no equivalentes.
Se intenta marcar (1,4)
(1,a) = 1
(4,a) = 5 Se marca (1,4)
(1,5) con X
Se intenta marcar (1,T)
(1,a) = 1 (1,b) = 2
(T,a) = T (T,b) = T Se marca (1,T)
(2,T) con X
Se intenta marcar (2,3)
(2,a) = 4 (2,b) = 3
(3,a) = 4 (3,b) = 3
Se intenta marcar (3,5)
(3,a) = 4 (3,b) = 3
(5,a) = T (5,b) = 5
Lista
de
espera
Se intenta marcar (2,5)
(2,a) = 4 (2,b) = 3
(5,a) = T (5,b) = 5
Se intenta marcar (4,T)
(4,a) = 5
(T,a) = T Se marcan
(4,T), (2,5)
(5,T) con X
2 3 4 5 T
1 X X X 2 X X 3 X X 4 X 5 X Son
equivalentes
X X
X X X
a 1 2 3
b
b b
a
4
5 b
a
a
T
a/b b
a
![Page 18: Diapositiva 1 - ecaths1.s3.amazonaws.comecaths1.s3.amazonaws.com/programacion2/851793929.U3-Automatas... · Un autómata finito (AF) es un modelo de computación muy restringido,](https://reader031.vdocumento.com/reader031/viewer/2022021903/5ba2aff209d3f2a1708c4b3d/html5/thumbnails/18.jpg)
17 17 14:17
a 1 23 4
b
b a
a
5
b
Los estados 2 y 3 que no están marcados significan que son equivalentes.
a
1 2 3
b
b b
a
4
5 b
a
a
T
a/b b
a
Autómata inicial
Autómata de Estados Mínimos
![Page 19: Diapositiva 1 - ecaths1.s3.amazonaws.comecaths1.s3.amazonaws.com/programacion2/851793929.U3-Automatas... · Un autómata finito (AF) es un modelo de computación muy restringido,](https://reader031.vdocumento.com/reader031/viewer/2022021903/5ba2aff209d3f2a1708c4b3d/html5/thumbnails/19.jpg)
18 18 14:17
Permiten realizar cálculos a partir de una cadena de entrada, o sea, traducen una
cadena de entrada en una cadena de salida.
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'.
Autómata Finito
Traductor
x
Lenguaje Regular
x’
![Page 20: Diapositiva 1 - ecaths1.s3.amazonaws.comecaths1.s3.amazonaws.com/programacion2/851793929.U3-Automatas... · Un autómata finito (AF) es un modelo de computación muy restringido,](https://reader031.vdocumento.com/reader031/viewer/2022021903/5ba2aff209d3f2a1708c4b3d/html5/thumbnails/20.jpg)
19 19 14:17
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.
La extensión natural de , * : Q x * O* se define:
*(q, ) =
*(q, xa) = *(q, x). ( e* (q, x), a)
Función de traducción para cadenas
EJEMPLO: Autómata finito traductor que calcula f(x) = 2x + 3 para x N, x > 0,
x representado en unario.
q0 q1
1|| 11111
1||11
x=1 traduce 11111
x=2 traduce1111111
A = ({q0 , q1), {1}, , q0 , {q1}, {1}, ) con:
(q0 ,1) = q1
(q1 ,1) = q1
(q0 ,1)=11111
(q1 ,1)=11
![Page 21: Diapositiva 1 - ecaths1.s3.amazonaws.comecaths1.s3.amazonaws.com/programacion2/851793929.U3-Automatas... · Un autómata finito (AF) es un modelo de computación muy restringido,](https://reader031.vdocumento.com/reader031/viewer/2022021903/5ba2aff209d3f2a1708c4b3d/html5/thumbnails/21.jpg)
20 20 14:17
Autómata Finito
Autómata Finito
Determinístico
Autómata Finito No
Determinístico
Autómata Finito de Estados Mínimos
Alg. para convertir
Autómata Finito
Gramáticas Regulares
Expresiones Regulares
Importancia Práctica: se usan para los Analizadores Léxicos.
Métodos