• Author / Uploaded
• ale184

Citation preview

AUTOMATAS FINITOS Definición Un autómata es una máquina, ya sea real o virtual, que se utiliza para el reconocimiento de patrones, es decir, buscar una cadena de símbolos determinada de entre varias válidas. Una aplicación real es la construcción de compiladores, que comprueban que las palabras reservadas de las estructuras estén bien puestas (parte del análisis léxico). En un Autómata se tiene que:  La entrada es un conjunto de patrones y La salida define si la entrada cumple o no cumple con una condición

AUTOMATAS FINITOS DETERMINISTAS

Definición formal Quíntupla M= (Q, , δ , q0, F) con Q : conjunto finito de estados  : alfabeto de la máquina δ : función de transición Qx Q q0 : estado inicial, q0 Q F : conjunto de estados de aceptación, F  Q δ (p,x) = q  M pasa del estado p al q al leer el símbolo x

AUTOMATAS FINITOS DETERMINISTAS

Definición formal M reconoce una cadena x1 x2 ... xn   una serie en S, s0, s1 ... sn con s0 = q0 sn F δ (sj-1, xj) = sj, j  [0, n] M reconoce un lenguaje si reconoce exclusivamente la colección de cadenas de dicho lenguaje.

AUTOMATAS FINITOS DETERMINISTAS

Definición formal Se deduce que... Todo autómata finito determinista definido para un alfabeto Σ con n símbolos debe contener al menos n transiciones. Un autómata finito determinista acepta la cadena vacía si y sólo si su estado inicial es un estado de aceptación.

AUTOMATAS FINITOS DETERMINISTAS

Diagrama de transiciones Diagrama que representa un autómata finito en términos de un grafo. Consiste en una colección finita de símbolos (que representan a los estados), que se pueden rotular con fines de referencia, conectados con flechas que reciben el nombre de arcos (que representan a las transiciones). Cada arco se etiqueta con un símbolo o categoría de símbolos que podría presentarse en la cadena de entrada que el autómata analiza. Uno de los estados se distingue con un apuntador y representa el estado inicial.

AUTOMATAS FINITOS DETERMINISTAS

Diagrama de transiciones Los denotados con círculos dobles designan estados en los cuales se ha reconocido una cadena válida (estados de aceptación). Habitualmente en estos diagramas sólo se representan las transiciones que conducen al reconocimiento de alguna cadena, considerándose implícito un denominado "estado de captación global", donde se entiende que llegan los arcos omitidos

AUTOMATAS FINITOS DETERMINISTAS

Tablas de transiciones Una tabla de transiciones es una representación tabular convencional de una función como δ, que recibe dos argumentos y devuelve un valor. Las filas de la tabla corresponden a los estados, y las columnas a las entradas. El valor correspondiente a la fila del estado q y a la columna de la entrada a es el estado δ(q, a).

AUTOMATAS FINITOS DETERMINISTAS

Diagrama de transiciones y tabla de transiciones AFD que acepta únicamente todas las cadenas de ceros y unos que contienen la secuencia 01 en algún lugar de la cadena: •Σ={0,1} • L={w|w tiene la forma x01y, donde x e y son cadenas que solo constan de los símbolos 0 y 1} 0

1 Inicio

q0

0

q2

0, 1 1

q1

El estado inicial se marca con una flecha, y los estados de aceptación con *.

AUTOMATAS FINITOS DETERMINISTAS

Búsqueda de una cadena valida en el diagrama de transiciones •La cadena 01 pertenece al lenguaje •La cadena 11010 pertenece al lenguaje •La cadena 100011 pertenece al lenguaje •La cadena ε no pertenece al lenguaje •La cadena 0 no pertenece al lenguaje •La cadena 111000 no pertenece al lenguaje 0

1 q0

0

q2

0, 1 1

q1

AUTOMATAS FINITOS DETERMINISTAS

Ejemplo: Máquina de refrescos No devuelve cambio Los refrescos valen $ 1 Admite monedas de $ 0.25, $ 0.5 y $ 1

Por lo que se tiene: Σ={$ 0.25, $ 0.5 y $ 1} L={w|w tiene como suma $ 1}

AUTOMATAS FINITOS DETERMINISTAS

Ejemplo: Máquina de refrescos Σ={$ 0.25, $ 0.5 y $ 1}

L={w|w tiene como suma $ 1}

inicio 1

q0

q1 0.5

0.5 0.25

0.25

q3 0.25 0.25

q2

0.5

q4

Suma acumulada: q0=0, q1=1, q2=0.25, q3=0.5, q4=0.75

AUTOMATAS FINITOS DETERMINISTAS

Ejemplo: Máquina de refrescos Σ={$ 0.25, $ 0.5 y $ 1}

1

q0

q1 0.5

0.5 0.25

L = { w | w tiene como suma $ 1}

* 0.25

q3 0.25 0.25

q2

0.5

q0 q1 q2 q3 q4

0.25 0.5 1 q2 q3 q1 error error error q3 q4 error q4 q1 error q1 error error

q4

Diagrama de transición

Tabla de transición

AUTOMATAS FINITOS DETERMINISTAS

Ejemplo: Sea el lenguaje A={(ab)i | i≥1}, el cual esta representado por la expresión regular (ab)+ a, b q3

b q2

a inicio

b q0

a q1

a

La cadena debe tener al menos una copia de ab: •Cadenas aceptadas : ab, abab, ababab, etc •Cadena no aceptadas : aa, aaab, abaa, abbab, etc

AUTOMATAS FINITOS DETERMINISTAS

Ejemplo: Sea el lenguaje A={(ab)i | i≥0}, el cual esta representado por la expresión regular (ab)* b inicio

a

q0 b

q1 a q2 a, b

*

δ

a

b

q0

q1

q2

q1

q2

q0

q2

q2

q2

La cadena debe tener cero o más copias de ab: •Cadenas aceptadas : ε, ab, abab, ababab, etc •Cadena no aceptadas : aa, aaab, abaa, abbab, etc

AUTOMATAS FINITOS DETERMINISTAS

Ejemplo: Reconoce números múltiplos de 3, compuestos por los dígitos 1, 2 y 3. δ 1 2 3 3 inicio

2

q0 2

q0 q1 q2 q3

q3

3

3

1

q1 q2 q3 q1

q2

1

1 2 q1

q2 q3 q1 q2

1 2 *

q3 q1 q2 q3

3

La suma de los dígitos debe ser múltiplo de 3: •Cadenas aceptadas : 12, 111, 1122, etc •Cadena no aceptadas : 232, 2321, 112333, etc

AUTOMATA FINITO NO DETERMINISTA

Definición Un autómata finito no determinista permite que desde un estado se realicen cero, una o más transiciones mediante el mismo símbolo de entrada. a

q1

b

q0 a q2

a

AUTOMATA FINITO NO DETERMINISTA

Definición formal Formalmente el autómata finito no determinista consiste en una quíntupla (S, Σ , ρ, i , F), donde S es un conjunto finito de estados Σ es el alfabeto de la máquina ρ es un subconjunto de S x Σ x S (posibles

transiciones de la máquina) i (un elemento de S) es el estado inicial F (un subconjunto de S) es la colección de estados de aceptación

AUTOMATA FINITO NO DETERMINISTA Ejemplo: AFN que acepta todas las cadenas que terminan en 01 inicio

0

q0

1

q1

q2

0, 1 Estados por los que pasa un AFN durante el proceso de la secuencia de entrada 00101 q0

q0

q0

q1

q0

q1 q2

0 Cadena aceptada

q0

q1

muere 0

q0

1

muere 0

q2 1

AUTOMATA FINITO NO DETERMINISTA Ejemplo: AFN que acepta todas las cadenas que terminan en 01 inicio

q0

0

1

q1

0, 1 Tabla de transición del AFN anterior

*

0

1

q0

{q0, q1}

{q0}

q1

Ø

{q2}

q2

Ø

Ø

q2