TEMA 4: AUTÓMATAS FINITOS (Parte A) María Llanos Alonso Díaz-Marta Antonio Fernández Caballero Departamento de Sistemas
Views 65 Downloads 4 File size 325KB
TEMA 4: AUTÓMATAS FINITOS (Parte A)
María Llanos Alonso Díaz-Marta Antonio Fernández Caballero Departamento de Sistemas Informáticos Universidad de Castilla-la Mancha Teoría de Autómatas y Lenguajes Formales
1
TEMA 4: AUTÓMATAS FINITOS INDICE z z z z z
Sistemas de estados finitos Autómatas finitos deterministas Autómatas finitos no deterministas Autómatas finitos con transiciones nulas AFND-ε Autómatas finitos y lenguajes regulares
Teoría de Autómatas y Lenguajes Formales
2
TEMA 4: AUTÓMATAS FINITOS SISTEMAS DE ESTADOS FINITOS (1) z Un Sistema de Estados Finitos es un dispositivo físico o lógico caracterizado porque, en un momento dado, puede encontrarse en un estado de entre un conjunto finito de ellos y éstos resumen el comportamiento del sistema hasta este instante dado. z Ejemplos: { Semáforo: (rojo, amarillo, verde). { Ascensor: (parado-piso-i, en-marcha). { Máquina expendedora: (espera, coge-dinero, sirve ...).
z Para caracterizar estos sistemas se usan modelos lógicos que simulan el comportamiento de un sistema de estados finitos. Teoría de Autómatas y Lenguajes Formales
3
TEMA 4: AUTÓMATAS FINITOS SISTEMAS DE ESTADOS FINITOS (2) z Un Autómata Finito es, en particular, un sistema de estados finitos que reconoce palabras, y, en general, un modelo matemático para describir sistemas de estados finitos. z Ejemplo de Sistema de Estados Finitos (SEF). Control de un ascensor { Estados: (parado-piso-i, enmarcha-hasta-i) { Acciones: (pulsar-botonpiso-i, stop)
Teoría de Autómatas y Lenguajes Formales
4
TEMA 4: AUTÓMATAS FINITOS SISTEMAS DE ESTADOS FINITOS (2) z Un Autómata Finito es, en particular, un sistema de estados finitos que reconoce palabras, y, en general, un modelo matemático para describir sistemas de estados finitos. z Ejemplo de Sistema de Estados Finitos (SEF). Control de un ascensor { Estados: (parado-piso-i, enmarcha-hasta-i) { Acciones: (pulsar-botonpiso-i, stop)
Teoría de Autómatas y Lenguajes Formales
5
TEMA 4: AUTÓMATAS FINITOS SISTEMAS DE ESTADOS FINITOS (2) z Un Autómata Finito es, en particular, un sistema de estados finitos que reconoce palabras, y, en general, un modelo matemático para describir sistemas de estados finitos. z Ejemplo de Sistema de Estados Finitos (SEF). Control de un ascensor { Estados: (parado-piso-i, enmarcha-hasta-i) { Acciones: (pulsar-botonpiso-i, stop)
Teoría de Autómatas y Lenguajes Formales
6
TEMA 4: AUTÓMATAS FINITOS SISTEMAS DE ESTADOS FINITOS (2) z Un Autómata Finito es, en particular, un sistema de estados finitos que reconoce palabras, y, en general, un modelo matemático para describir sistemas de estados finitos. z Ejemplo de Sistema de Estados Finitos (SEF). Control de un ascensor { Estados: (parado-piso-i, enmarcha-hasta-i) { Acciones: (pulsar-botonpiso-i, stop)
Teoría de Autómatas y Lenguajes Formales
7
TEMA 4: AUTÓMATAS FINITOS SISTEMAS DE ESTADOS FINITOS (2) z Un Autómata Finito es, en particular, un sistema de estados finitos que reconoce palabras, y, en general, un modelo matemático para describir sistemas de estados finitos. z Ejemplo de Sistema de Estados Finitos (SEF). Control de un ascensor { Estados: (parado-piso-i, enmarcha-hasta-i) { Acciones: (pulsar-botonpiso-i, stop)
Teoría de Autómatas y Lenguajes Formales
8
TEMA 4: AUTÓMATAS FINITOS AUTÓMATAS FINITOS DETERMINISTAS (1) DESCRIPCIÓN INFORMAL zUn Autómata Finito Determinista es un SEF que “reconoce palabras de un determinado lenguaje”. Se denomina determinista porque su comportamiento queda determinado conocida la entrada. zSe compone de: { Una Cinta de entrada dividida en celdas, la cual contiene la “palabra” de entrada (un símbolo por cada celda y desde la izquierda). { Una Cabeza lectora, la cual apunta a una celda de la cinta determinada. { Un Control finito; es como una “caja negra” que contiene el mecanismo de “transición” entre los estados en donde puede “permanecer”. Teoría de Autómatas y Lenguajes Formales
9
TEMA 4: AUTÓMATAS FINITOS AUTÓMATAS FINITOS DETERMINISTAS (2) a
a
a
b
b
Cabeza lectora Control Autómata finito Estado: Inicial
Teoría de Autómatas y Lenguajes Formales
10
TEMA 4: AUTÓMATAS FINITOS AUTÓMATAS FINITOS DETERMINISTAS (2) a
a
a
b
b
Cabeza lectora Control Autómata finito Estado: Tras leer a
Teoría de Autómatas y Lenguajes Formales
11
TEMA 4: AUTÓMATAS FINITOS AUTÓMATAS FINITOS DETERMINISTAS (2) a
a
a
b
b
Cabeza lectora Control Autómata finito Estado: Siguiente a
Teoría de Autómatas y Lenguajes Formales
12
TEMA 4: AUTÓMATAS FINITOS AUTÓMATAS FINITOS DETERMINISTAS (2) a
a
a
b
b Cabeza lectora Control
Autómata finito Estado: Aceptado
Teoría de Autómatas y Lenguajes Formales
13
TEMA 4: AUTÓMATAS FINITOS AUTÓMATAS FINITOS DETERMINISTAS (3) zFuncionamiento: Cada lenguaje tiene asociado (al menos) un Autómata Finito. {Lee los símbolos de entrada de izquierda a derecha. {Cambia de estado con cada símbolo. {Según el tipo de estado en donde quede tras el último símbolo leído, se decide si la palabra se acepta o no. {Para leer una palabra de n símbolos, el AF realiza n transiciones, visitando (el control) n+1 estados. Teoría de Autómatas y Lenguajes Formales
14
TEMA 4: AUTÓMATAS FINITOS AUTÓMATAS FINITOS DETERMINISTAS (4) a1, a2, …, an
a1, a2, …, an
a1, a2, …, an …….
q0
⇒
qi1
⇒
Teoría de Autómatas y Lenguajes Formales
qin-
1
⇒
qF
15
TEMA 4: AUTÓMATAS FINITOS AUTÓMATAS FINITOS DETERMINISTAS (5) DESCRIPCIÓN FORMAL z Un AFD es una quíntupla M = (Q, Σ, δ, q0, F) donde: z Q: Conjunto finito y no vacío de estados {q0, q1, …, qn-1}. z Σ: Alfabeto de entrada: conjunto finito y no vacío de símbolos. z q0 ∈ Q: Estado inicial. z F ⊆ Q: Subconjunto de estados finales. z δ: Función de transición: reglas de cambio de estados. δ: Q x Σ → Q (totalmente definida) donde, si δ(p, a) = q, significa que el AFD pasa del estado p al estado q cuando lee la entrada a. Teoría de Autómatas y Lenguajes Formales
16
TEMA 4: AUTÓMATAS FINITOS AUTÓMATAS FINITOS DETERMINISTAS (6) z El término determinista hace referencia a que desde un estado p ∈ Q y una entrada a ∈ Σ, el AFD cambia de forma única y determinista a uno y solo uno de los estados de Q. z La simplicidad del AFD radica en que, para cambiar de estado, basta conocer el estado actual y el símbolo de entrada correspondiente, sin necesidad de conocer qué ha pasado hasta este momento (no hace falta memoria adicional).
Teoría de Autómatas y Lenguajes Formales
17
TEMA 4: AUTÓMATAS FINITOS AUTÓMATAS FINITOS DETERMINISTAS (7) REPRESENTACIÓN (1) z Un AFD M = (Q, Σ, δ, q0, F) puede representarse: a): Como un grafo dirigido: Los nodos son los estados Q y las aristas son ternas (p,q,a) ⇔ δ(p, a) = q, donde p,q ∈Q y a ∈ Σ.
z Existen estados no finales a donde va cualquier salida no indicada, denominados estados sumideros Teoría de Autómatas y Lenguajes Formales
18
TEMA 4: AUTÓMATAS FINITOS EJEMPLO z Consideremos el AFD M = ({q0,q1,q2,q3}, {a,b}, δ, q0, {q2}), donde δ viene dada por: δ(q0,a) = q1 δ(q0,b) = q3 δ(q1,a) = q2 δ(q1,b) = q1 δ(q2,a) = q3 δ(q2,b) = q3 δ(q3,a) = q3 δ(q3,b) = q3 Representar este AFD mediante un grafo dirigido.
Teoría de Autómatas y Lenguajes Formales
19
TEMA 4: AUTÓMATAS FINITOS AUTÓMATAS FINITOS DETERMINISTAS (8) REPRESENTACIÓN (2) z Un AFD M = (Q, Σ, δ, q0, F) puede representarse: b): Como una tabla de transiciones de la función de transición δ, en donde: { Las columnas están etiquetas por los símbolos de Σ. { Las filas están etiquetadas por los estados de Q. { El estado inicial se simboliza anteponiendo al símbolo la marca >. { Los estados finales con la marca *. { Una casilla [p,a], contendrá q si y solo si δ(p, a) = q con p,q ∈ Q y a ∈ Σ. Teoría de Autómatas y Lenguajes Formales
20
TEMA 4: AUTÓMATAS FINITOS EJEMPLO M1 = ({q0,q1,q2}, {a,b}, δ, q0, {q0,q1})
Teoría de Autómatas y Lenguajes Formales
21
TEMA 4: AUTÓMATAS FINITOS AUTÓMATAS FINITOS DETERMINISTAS (9) LENGUAJE ACEPTADO POR UN AFD (1) zSea un AFD M = (Q, Σ, δ, q0, F).
{ Una descripción instantánea (DI) es un par (q,α) que define la situación de M en un instante dado en el reconocimiento de una palabra ω ∈ Σ, en donde q es el estado actual y α es el sufijo de ω que falta por leer. { Se denomina transición válida a la relación ├M entre dos DI’s definida como: (q,aα) ├M (p,α) ⇔ δ(q, a) = p. { A partir de ├M se define, de forma natural, el cierre reflexivo y transitivo, ├*M: Si I1, I2 son dos DI’s, entonces I1├*M I2 ⇔ ∃J1, J2,…, Jn DI’s | I1 = J1├M J2…├M Jn = I2, con n ≥ 0. Teoría de Autómatas y Lenguajes Formales
22
TEMA 4: AUTÓMATAS FINITOS EJEMPLO Si tenemos el siguiente AFD:
tenemos que (q0,aabb)├ (q0,abb)├ (q0,bb)├ (q1,b) Teoría de Autómatas y Lenguajes Formales
23
TEMA 4: AUTÓMATAS FINITOS AUTÓMATAS FINITOS DETERMINISTAS (10) LENGUAJE ACEPTADO POR UN AFD (2) z Veremos ahora otra forma equivalente de definir el Lenguaje aceptado por un AFD. z Definiremos Función de transición extendida a palabras de δ y lo notaremos como δ∗ a una función: δ∗: Q x Σ∗ → Q como 1. δ∗(q, ε) = q 2. δ∗(q, αa) = δ(δ∗(q,α),a), ∀q ∈ Q, α ∈ Σ∗, a ∈ Σ 3. Equivalentemente: δ∗(q,aα) = δ∗(δ(q,a),α), ∀q ∈ Q, α ∈ Σ∗, a ∈ Σ Teoría de Autómatas y Lenguajes Formales
24
TEMA 4: AUTÓMATAS FINITOS
EJEMPLO
δ∗(q0,abb) = δ(δ∗(q0,ab),b) = δ(δ(δ(δ∗(q0,ε),a),b),b) = q1
Teoría de Autómatas y Lenguajes Formales
25
TEMA 4: AUTÓMATAS FINITOS AUTÓMATAS FINITOS DETERMINISTAS (11) LENGUAJE ACEPTADO POR UN AFD (3) z Segunda definición de Lenguaje aceptado por un AFD a partir de la definición de δ∗. z Una palabra ω ∈ Σ∗ es aceptada por un AFD M si δ∗(q0,ω) ∈ F. z Se define el Lenguaje aceptado por M al conjunto: L(M) = { ω ∈ Σ∗ | δ∗(q0,ω) ∈ F }
Teoría de Autómatas y Lenguajes Formales
26
TEMA 4: AUTÓMATAS FINITOS EJEMPLO (1) z Construir un AFD para reconocer las cadenas binarias que tengan un número impar de unos. {Alfabeto de entrada será: Σ = {0,1} {Los estados tienen que representar las posibles situaciones: zLa subcadena leída hasta ahora tiene número par de unos q0 zLa subcadena leída hasta ahora tiene número impar de unos q1 1
0
q1 0
q0 1
Teoría de Autómatas y Lenguajes Formales
27
TEMA 4: AUTÓMATAS FINITOS EJEMPLO (1) z Construir un AFD para reconocer las cadenas binarias que tengan un número impar de unos. {Alfabeto de entrada será: Σ = {0,1} {Los estados tienen que representar las posibles situaciones: zLa subcadena leída hasta ahora tiene número par de unos q0 zLa subcadena leída hasta ahora tiene número impar de unos q1 1
0
q1 0
q0 1
Teoría de Autómatas y Lenguajes Formales
28
TEMA 4: AUTÓMATAS FINITOS EJEMPLO (2) zConstruir un AFD para reconocer las cadenas válidas de ADN. zUna cadena de ADN está formada por dos cadenas. zLa información genética reside en el orden en que aparecen las cuatro bases Adenina, Timina, Guanina y Citosina. zAdemás se conoce que por condicionante químicos la Adenina sólo puede emparejarse con la Timina y la Citosina con la Guanina. zNo permitimos la cadena ε. Teoría de Autómatas y Lenguajes Formales
29
TEMA 4: AUTÓMATAS FINITOS EJEMPLO (2)
Teoría de Autómatas y Lenguajes Formales
30
TEMA 4: AUTÓMATAS FINITOS EJEMPLO (2)
Teoría de Autómatas y Lenguajes Formales
31
TEMA 4: AUTÓMATAS FINITOS EJEMPLO (2)
Teoría de Autómatas y Lenguajes Formales
32
TEMA 4: AUTÓMATAS FINITOS EJEMPLO (3) zRepresentar el autómata finito que genera el lenguaje L = {abna | n ≥ 0}. a
q0
q1
b
b
a a,b
a,b
q2
q3
Teoría de Autómatas y Lenguajes Formales
33
TEMA 4: AUTÓMATAS FINITOS PROBLEMAS 1. Dados los siguientes AFD AFD1 = ( {A,B}, {a,b,c}, δ1, A, {B} ) AFD2 = ( {A,B}, {a,b,c}, δ2, A, {B} ) δ1
a
b
c
δ2
a
b
c
A
A
B
A
A
B
A
A
B
B
B
B
B
B
B
B
Determinar el lenguaje aceptado por cada uno de ellos. Teoría de Autómatas y Lenguajes Formales
34
TEMA 4: AUTÓMATAS FINITOS PROBLEMAS 2. Construir los AFD que acepten los siguientes lenguajes con el alfabeto {0,1}. a) El conjunto de todas las cadenas terminadas en 00. b) El conjunto de todas las cadenas con tres ceros consecutivos. c) El conjunto de todas las cadenas en las que el número de ceros sea divisible por 5 y el número de unos sea divisible por 3. d) El conjunto de todas las cadenas que comiencen por 1 y que, si se interpretan como la representación binaria de un entero, sean múltiplos de 5 (Ejemplo: 101, 1010, 1111).
Teoría de Autómatas y Lenguajes Formales
35
TEMA 4: AUTÓMATAS FINITOS AUTÓMATAS FINITOS DETERMINISTAS (12) ESTADOS ACCESIBLES. AUTÓMATA CONEXO Sea un AFD M, entonces: z Un estado q ∈ Q es accesible desde otro estado p ∈ Q si existe una palabra ω ∈ Σ* tal que δ∗(p,ω) = q. z Nota: Cualquier estado es siempre accesible desde él mismo a través de la palabra vacía ε. z Un AFD es conexo si cualquiera de sus estados es accesible desde el estado inicial q0.
Teoría de Autómatas y Lenguajes Formales
36
TEMA 4: AUTÓMATAS FINITOS EJEMPLO
Teoría de Autómatas y Lenguajes Formales
37
TEMA 4: AUTÓMATAS FINITOS AUTÓMATAS FINITOS DETERMINISTAS (13) AFD CONEXO EQUIVALENTE (1) z Sea un AFD M. Llamaremos Mc al subautómata conexo de M donde: { Qc = {q | q ∈ Q y q es accesible en M desde q0} { Σc = Σ { q0c = q0 { Fc = F ∩ Qc { δc será una restricción de δ a Qc x Σc → Qc
Teoría de Autómatas y Lenguajes Formales
38
TEMA 4: AUTÓMATAS FINITOS AUTÓMATAS FINITOS DETERMINISTAS (14) AFD CONEXO EQUIVALENTE (2) z Propiedad: Dado un AFD M siempre existe un AFD conexo Mc equivalente a M. Demostraremos la doble inclusión:
⇒ Si x ∈ L(M) ⇒ δ* (q0, x) ∈ F ⇒ δ* (q0, x) = p ∈ F, entonces p es accesible ⇒ δ* (q0, x) ∈ F ∩ Qc ⇒ δ* (q0, x) ∈ Fc ⇒ x ∈ L(Mc) ⇐ Si x ∈ L(Mc) ⇒ δ* (q0, x) ∈ Fc ⊆ F ⇒ δ* (q0, x) ∈ F ⇒ x ∈ L(M) Teoría de Autómatas y Lenguajes Formales
39
TEMA 4: AUTÓMATAS FINITOS AUTÓMATAS FINITOS DETERMINISTAS (15) ALGORITMO PARA AFD CONEXO EQUIVALENTE z Veremos un algoritmo que, basado en la definición de AFD conexo, busca en “anchura” en el grafo desde q0 hasta completar todos los posibles caminos dirigidos desde este estado inicial. Dado un AFD M = (Q, Σ, δ, q0, F) calcular el AFD conexo Mc = (Qc, Σ, δc, q0, Fc). 1. Qc = {q0} e i = 0, número de fila. 2. Mientras hay estado qj ∈ Qc y qj no esté en la tabla, hacer: a) Crear una fila i en la tabla para qj b) Rellenar fila i con los estados Ei = {q | δ(qj , a) = q, a ∈ Σ} c) Etiquetar nuevas filas con los estados Nuevos = Ei - Qc d) Qc = Qc∪ Nuevos e i = i + 1 3. Fc = F ∩ Qc Teoría de Autómatas y Lenguajes Formales
40
TEMA 4: AUTÓMATAS FINITOS EJEMPLO
Construir el AFD conexo Mc para el siguiente AFD:
Teoría de Autómatas y Lenguajes Formales
41
TEMA 4: AUTÓMATAS FINITOS AUTÓMATAS FINITOS DETERMINISTAS (16) MINIMIZACIÓN DE AFDs (1) z Dado un AFD M podemos intuir que varios estados se pueden “comportar” de similar manera ante una palabra o subpalabra ω ∈ Σ∗ de entrada. z Informalmente, dos estados p y q serán equivalentes si, cuando estamos reconociendo una palabra ω, lo que ocurra tras leer ω desde p es lo mismo que leer ω desde q.
Teoría de Autómatas y Lenguajes Formales
42
TEMA 4: AUTÓMATAS FINITOS AUTÓMATAS FINITOS DETERMINISTAS (17) MINIMIZACIÓN DE AFDs (2) zFormalmente: Hemos de definir la relación E. Dos estados son equivalentes y lo notamos por pEq si: ∀x ∈ Σ∗, δ*(p, x) ∈ F ⇔ δ*(q, x) ∈ F zDos estados son equivalentes en longitud n y lo notaremos como pEnq si: ∀x ∈ Σ∗, |x| ≤ n, δ*(p, x) ∈ F ⇔ δ*(q, x) ∈ F zA partir de las definiciones anteriores, se sigue que pEq ⇒ pEnq, ∀n, y también que pEnq ⇒ pEkq, ∀k < n. Teoría de Autómatas y Lenguajes Formales
43
TEMA 4: AUTÓMATAS FINITOS EJEMPLO 1
>
q0 0
0,1
q1 0
q3
1
0
q2
Teoría de Autómatas y Lenguajes Formales
1
44
TEMA 4: AUTÓMATAS FINITOS AUTÓMATAS FINITOS DETERMINISTAS (18) MINIMIZACIÓN DE AFDs (3) z Dado un AFD M. Las relaciones E y Ei son relaciones de equivalencia. Por lo tanto existen los conjuntos cocientes Q´ = Q/E y Qi = Q/Ei . Q/E0 = Q0 = {Q00, Q01, ...} Q/E1 = Q1 = {Q10, Q11, ...} ... Q/Em, = Qm = {Qm0, Qm1, ...} z Se sabe que: Si pEi+1q ⇒ pEiq. z Dado Qi = {Qi0, Qi1, ... , Qim} y p, q ∈ Qij , entonces se cumple: pEi+1q ⇔ ∀a ∈ Σ, ∃Qik ∈ Qi | δ(p, a), δ(q, a) ∈ Qik z Esto significa que podemos obtener Qi+1 a partir de Qi, empezando por Q0. Teoría de Autómatas y Lenguajes Formales
45
TEMA 4: AUTÓMATAS FINITOS AUTÓMATAS FINITOS DETERMINISTAS (19) MINIMIZACIÓN DE AFDs (4) ALGORITMO DEL CALCULO DE LOS CONJUNTOS COCIENTES Qi
1. Q0 = { Q-F, F }, i = 0 2. Mientras haya cambios (Qi ≠ Qi+1) a) Qi = { Qi0, Qi1, ・・・Qim } b) Para cada Qij ∈ Qi hacer subgrupos S1, S2, ..., Sh tales que: p, q ∈ Sr ⇔ ∀a ∈ Σ, ∃Qik | δ (p, a) ∧ δ (q, a) ∈ Qik c) i = i + 1 Teoría de Autómatas y Lenguajes Formales
46
TEMA 4: AUTÓMATAS FINITOS EJEMPLO (1) Calcular las clases de equivalencia Q/E del AFD: Paso 1: Q0 Q00 = {q0, q1, q2} (no finales) ; Q01 = {q3} (finales) Paso 2: Q1 1
>
q0 0
0,1
q1 0
q3
Q00
1
0
q2
Q01
δ
0
1
q0
Q01
Q00
q1
Q01
Q00
q2
Q01
Q00
q3
Q01
Q01
Q10 = Q00 ; Q11 = Q01
1
Paso 3: Q1 = Q0 ⇒ FIN
Teoría de Autómatas y Lenguajes Formales
47
TEMA 4: AUTÓMATAS FINITOS EJEMPLO (2) Calcular las clases de equivalencia Q/E del AFD: 0
>
q0
q1
0
1 q2
1 1
0
q3
0 0
q4
1 1
q5
Teoría de Autómatas y Lenguajes Formales
0,1
48
TEMA 4: AUTÓMATAS FINITOS AUTÓMATAS FINITOS DETERMINISTAS (20) MINIMIZACIÓN DE AFDs (5) z Entrada: AFD M = (Q, Σ, δ, q0, F). z Salida: AFD M’ = (Q’, Σ, δ’, q’0, F’) tal que L(M) = L(M’) y |Q’| ≤ |Q|. 1. Eliminar de Q todos los estados inaccesibles desde q0. Es decir, obtener Mc de M. 2. Construir Q’ = Q/E de Mc. 3. Construir el autómata M’ como sigue: z Q’ = Q/E = {Q’0, Q’1, ..., Q’n} z q’0 = Q’i ∈ Q’ con q0 ∈ Q’i z F’ = {Q’i ∈ Q’ con Q’i ⊆ F} z δ’(Q’i,a) = Q’j ⇔ ∃p ∈ Q’i tal que δ(p,a) ∈ Q’j Teoría de Autómatas y Lenguajes Formales
49
TEMA 4: AUTÓMATAS FINITOS EJEMPLO Minimizar el siguiente AFD: 0
>
q0
q1
0
1 q2
1 1
0
q3
0 0
q4
1 1
q5
Teoría de Autómatas y Lenguajes Formales
0,1
50