Automatas Finitos

Cap´ ıtulo 2

Aut´matas Finitos y o Expresiones Regulares
2.1. Aut´matas Finitos Deterministas. o

En esta asignatura se estudiar´n distintos tipos de m´quinas abstractas con difea a rente poder computacional. Cada uno de estos tipos de m´quinas permiten reconocer a lenguajes de distintos tipos y su poder computacional est´ asociado a cu´l es el tipo a a de lenguajes que pueden reconocer. Elprimer tipo de m´quinas abstractas que se va a definir son los Aut´matas a o Finitos, que permiten reconocer cadenas pertenecientes a Lenguajes Regulares. Son los aut´matas con menor poder computacional y para reconocer los lenguajes o s´lo disponen de una cinta de entrada (en la que se escribe una cadena), de un cabezal o lector (que lee s´ ımbolos de uno en uno y de izquierda a derecha) y de unconjunto finito de reglas que especifica c´mo actuar ante cada s´ o ımbolo le´ de la cinta de ıdo entrada. Gr´ficamente se puede representar por medio de la siguiente figura: a

Cinta de entrada

a b b b a a
Cabezal de Lectura

Control Finito

Figura 2.1: Modelo f´ ısico de un Aut´mata Finito. o

15

16

Cap´ ıtulo 2. Aut´matas Finitos y Expresiones Regulares o

Definici´n 2.1 Unaut´mata finito determinista, AFD, es una qu´ o o ıntupla A = Σ, Q, f, q0 , F donde: Σ es el alfabeto de entrada, Q es un conjunto finito y no vac´ de estados, ıo f es una funci´n total definida como o f : Q × Σ → Q, q0 es el denominado estado inicial, q0 ∈ Q, F es el conjunto de estados denominados finales, F ⊆ Q.

La forma m´s generalizada de representaci´n de un AFD es mediante un grafo a o dirigido.En este grafo los nodos se corresponden con los estados de Q y los arcos representan valores de la funci´n de transici´n f, de forma que si f (qs , a) = qt o o entonces desde el nodo qs parte un arco etiquetado con el s´ ımbolo a hacia el nodo qt . Los estados de F se representan mediante nodos con doble c´ ırculo y el estado inicial se suele representar con una flecha de entrada al nodo que lorepresenta. Ejemplo: Sea A el siguiente AFD Q = {q0 , q1 , q2 } F = {q0 , q1 } Σ = {0, 1} q0 ∈ Q, es el estado inicial en el que la funci´n de transici´n f se define como: o o f q0 q1 q2 0 1 q0 q1 q2 q1 q2 q2

Este AFD se puede representar mediante el siguiente grafo:

0

1 1

0,1 0

q0

q1

q2

2.1. Aut´matas Finitos Deterministas. o

17

Para poder determinar cu´l es el conjuntode cadenas aceptadas por un aut´mata a o se necesita estudiar cu´l es su comportamiento ante cadenas de s´ a ımbolos. Se define f como la extensi´n de la funci´n de transici´n que se aplica a cadenas de s´ o o o ımbolos del alfabeto, f : Q × Σ∗ → Q a)f (q, λ) = q, ∀ q ∈ Q b)f (q, xa) = f (f (q, x), a), x ∈ Σ∗ , a ∈ Σ De esta forma, en el aut´mata finito del ejemplo anterior o f (q0 , 011) = f (f (f(f (q0 , λ), 0), 1), 1) = q1 . Para simplificar la notaci´n se utiliza el mismo s´ o ımbolo de funci´n f para referirse o tanto a f como a f . Definici´n 2.2 Se define el lenguaje aceptado por un AFD A = Σ, Q, f, q0 , F o como el conjunto de cadenas tales que despu´s de ser analizadas el AFD se e encuentra en un estado final; es decir, L(A) = {x ∈ Σ∗ | f (q0 , x) ∈ F }

Ejemplo: ¿Qu´ lenguajesreconocen los siguientes AFD? e

EL AFD del caso (a) reconoce las cadenas que tienen el formato (10)n con n ≥ 1, es decir La = {10, 1010, 101010, 10101010, . . .}.

18

Cap´ ıtulo 2. Aut´matas Finitos y Expresiones Regulares o

EL AFD del caso (b) acepta las cadenas que presentan el formato bcan y las cadenas del formato acm , con n, m ≥ 0. El AFD del caso (c) resulta m´s dif´ de describir deforma general. a ıcil Algunas de las cadenas que acepta son Lc = {acacbdbcaca, aaacaaacccbdddddbcaaaca, . . .}. Aquellos estados que no sean finales y que, adem´s, una vez que son alcanzados a el AFD permanece en ellos, sean cuales sean los s´ ımbolos que se lean de la entrada, se denominan estados sumideros. Como convenio no suelen mostrarse en el grafo para as´ poder minimizar el n´mero de...