Rapido

CIENCIAS DE LA COMPUTACION I

2007

AUTOMATAS FINITOS
Un autómata finito es un modelo matemático de una máquina que acepta cadenas de un lenguaje definido sobre un alfabeto A. Consiste en un conjunto finito de estados y un conjunto de transiciones entre esos estados, que dependen de los símbolos de la cadena de entrada. El autómata finito acepta una cadena x si la secuencia de transicionescorrespondientes a los símbolos de x conduce desde el estado inicial a un estado final. Si para todo estado del autómata existe como máximo una transición definida para cada símbolo del alfabeto, se dice que el autómata es determinístico (AFD). Si a partir de algún estado y para el mismo símbolo de entrada, se definen dos o más transiciones se dice que el autómata es no determinístico (AFND).Formalmente un autómata finito se define como una 5-upla M = donde E: conjunto finito de estados A: alfabeto o conjunto finito de símbolos de entrada δ: función de transición de estados, que se define como - δ: E x A → E si el autómata es determinístico - δ: E x A → P(E) si el autómata es no determinístico (P(E) es el conjunto potencia de E, es decir el conjunto de todos los subconjuntos de E) e0:estado inicial; e0 ∈ E F: conjunto de estados finales o estados de aceptación; F ⊆ E Generalmente se asocia con cada autómata un grafo dirigido, llamado diagrama de transición de estados. Cada nodo del grafo corresponde a un estado. El estado inicial se indica mediante una flecha que no tiene nodo origen. Los estados finales se representan con un círculo doble. Si existe una transición del estado eial estado ej para un símbolo de entrada a, existe entonces un arco rotulado a desde el nodo ei al nodo ej; es decir que δ(ei, a) = ej, se representa en el diagrama ei a ej

Ejemplo 1: Autómata finito determinístico que acepta el lenguaje L1 = {ancbm/ n > 0 y m ≥ 0 } M1D = < {e0, e1, e2}, {a, b, c}, δ1D, e0, {e2 }> δ1D está definida por el siguiente diagrama de transición de estados a e0 a e1 c be2

Ejemplo 2: Autómata finito determinístico que acepta el lenguaje

CIENCIAS DE LA COMPUTACION I

2007

L2 = {00x1/ x ∈ {0, 1}* } M2D = < {e0, e1, e2, e3}, {0, 1}, δ2D, e0, {e3 }> δ2D está definida por el siguiente diagrama de transición de estados 1 0 1 0 0 e1 e3 e2 e0 0 Ejemplo 3: Autómata finito determinístico que acepta el lenguaje L3 = {xc3m/ x ∈ {a, b}* y la cantidad de b’s espar y m ≥ 0} M3D = < {e0, e1, e2, e3, e4}, {a, b, c}, δ3D, e0, {e0, e4}> δ3D está definida por el siguiente diagrama de transición de estados a a e0 b b e1 c e2 c e3 c Ejemplo 4: Autómata finito no determinístico que acepta el lenguaje L4 = { x / x ∈ {0, 1}* y x contiene la subcadena 00 ó x contiene la subcadena 11} M4ND = < {e0, e1, e2, e3, e4}, {0, 1}, δ4ND, e0, {e2, e4 }> δ4ND está definida porel siguiente diagrama de transición de estados 0, 1 e0 1 e1 1 e2 0, 1 0 e3 0 e4 0, 1 c e4

Función de transición para cadenas Se define además una función δ*: E x A* → E, tal que δ* (ei, x) es el estado en que estará el autómata después de leer la cadena x comenzando en el estado ei. 1) δ* (ei, ε) = ei 2) δ* (ei, xa) = δ(δ* (ei,x), a) siendo x una cadena y a un símbolo del alfabeto A. Ladiferencia 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. El lenguaje aceptado por un autómata finito M = es:

CIENCIAS DE LA COMPUTACION I

2007

L(M) = { x ∈ A* / δ* (e0, x) ∈ F } Los lenguajes aceptados por autómatas finitos se denominan lenguajes regulares.

Equivalencia entre AFD y AFND Para cada AFND,existe un AFD que acepta el mismo lenguaje. Dado el autómata finito no determinístico MND = , se define el autómata finito determinístico correspondiente MD= como sigue: - ED = P(END) (conjunto potencia de END). Cada elemento de ED se representa como [e1, e2, ..., ei] donde e1, e2, ..., ei están en END. Se debe notar que [e1, e2, ..., ei] es un único estado de MD que corresponde a un conjunto de...