| INSTITUTO POLITÉCNICO NACIONAL ESCUELA SUPERIOR DE CÓMPUTO |

Introducción | Contenido | Bibliografía

Introducción
Contenido
UNIDAD I
UNIDAD II
UNIDAD III Introducción 3.1 Token y Lexemas 3.2 Algoritmo de los dos Buffers 3.3 Expresiones regulares

3.4 Definición y ejemplos de AFN

3.5 Definición y ejemplos de AFD

3.6 Construcción de un AFN a partir de una expresión regular

3.7 Conversión de un AFN a AFD (Construcción de subconjuntos)

3.8 Lenguaje LEX

3.9 Escritura de Programas LEX

UNIDAD IV
UNIDAD V
UNIDAD VI
UNIDAD VII
UNIDAD VIII
UNIDAD IX
PROBLEMARIO
Bibliografía

3.5 Definición y ejemplos de AFD

> El término determinístico se refiere al hecho de que para cada símbolo de entrada el autómata solo puede transitar a uno y solo un estado, y donde no existen transiciones con el carácter vacio.

> Un autómata finito determinístico (AFD) funciona de la siguiente manera: la información que recibe la máquina viene codificada en símbolos de un alfabeto que se escriben en una cinta de entrada divida en cuadrados (en número ilimitado) y se escribe un símbolo en cada cuadrado (casilla). La parte principal de la máquina es una “caja negra”, llamada unidad de control finito, que presenta, en cada momento específico, un estado concreto del conjunto de estados posibles K.

> La unidad de control finito puede conocer el símbolo escrito en la casilla correspondiente de la cinta de entrada mediante una cabeza de lectura movible. Inicialmente, la cabeza grabadora se coloca al comienzo de la cinta y la unidad de control finito se encuentra en el estado inicial. A continuación el autómata lee el símbolo de la primera casilla y la unidad de control finito pasa a un nuevo estado que viene especificado por su función de transición; el nuevo estado depende del estado previo y del símbolo leído. Entonces la cabeza de lectura se mueve una casilla a la derecha y lee el símbolo escrito en dicha casilla. Este proceso se va repitiendo a intervalos regulares, se lee un símbolo, la unidad de control finito actualiza su estado y la cabeza de lectura pasa a la casilla siguiente, así sucesivamente hasta que la cabeza de lectura llega al final de la cadena de símbolo escritos en la cinta de entrada.

> El autómata acepta (aprueba), o no (desaprueba), la cadena de símbolos de entrada (palabra) según que el estado que presenta la unidad de control finito sea, o no, un estado del conjunto final de estados F. El conjunto de palabras (cadenas de símbolos) que acepta un autómata finito determinístico constituye el lenguaje aceptado por la máquina.

> Un autómata finito determinístico A = (Q, ∑, δ, qs, F) consiste de:

> 1. Un conjunto finito de estados Q.

> 2. Un conjunto finito de símbolos (alfabeto) ∑.

> 3. Una función de transición δ que toma como argumentos un estado y un símbolo y devuelve un estado. La función δ es un mapeo de Q × ∑ a Q.

> 4. Un estado inicial qs perteneciente a Q.

> 5. Un conjunto de estados finales (o de aceptación) F con F Q.

> La función de transición δ normalmente se especifica ya sea como un diagrama de transiciones o como una tabla de transiciones.

> Diagrama de transiciones

> Un diagrama de transiciones para un autómata deterministico A es un grafo definido como:

> a) Para cada estado q Q hay un nodo.

> b) Para cada estado p, q Q y cada símbolo a ∑ con una transición dada por δ(q, a) = p, existe un arco desde el nodo q hasta el nodo p marcado con el símbolo a. Nota: Si hay varios símbolos que llevan desde q hasta p entonces el arco se marca con la lista de símbolos.

> c) Existe un arco llamado partida que apunta hacia el estado inicial.

> d) Los nodos que indican estados finales se denotan con círculos dobles.

> Tabla de transición

> La función de transición δ puede escribirse como una tabla en que cada línea indica un estado y se indica cual es el próximo estado para cada uno de los símbolos del alfabeto.

|  | alfabeto |
| Estados Q | 0 | 1
→ | q0 | q2 | q1
| q1 | q3 | q0
| q2 | q0 | q3
* | q3 | q1 | q2

> La flecha indica el estado inicial y los estados con asteriscos son estados finales.

> Ahora surge la siguiente pregunta: ¿Qué propiedades tienen los lenguajes aceptados por un autómata finito determinista?

> Esta pregunta se responde si se puede demostrar que son cerrados bajos las siguientes operaciones unión, intersección, complementación, concatenación y la operación estrella de Kleene.

> Por otra parte, la clase de los lenguajes regulares (o conjuntos regulares) sobre un alfabeto Σ es el conjunto minimal de lenguajes que contienen a φ, a todos los conjuntos formados por un solo símbolo, {a}, para a Σ, y son cerrados bajo las operaciones de unión, concatenación y estrella de Kleene. Así, un resultado importante (Lewis y Papadimitriou) es que un lenguaje es regular, siempre y cuando sea aceptado por un autómata finito.

> Ejemplo 1:

> Construir un autómata finito M que acepte el conjunto de cadenas binarias cuya cantidad de ceros es impar y cuya cantidad de unos es par.

> Más formalmente, se desea construir M: AF / L(M) = L sobre Σ = {0, 1} donde L={ α ε Σ* / | Π{0} (α) | es impar | Π{1} (α) | es par }.

> Para resolver este problema se siguen los pasos:

> Paso 1. Se quiere aceptar al conjunto de cadenas que satisface la conjunción.
> P= I0 P1 donde: I0 es “α tiene cantidad impar de ceros” y P1 es “α tiene cantidad par de unos” o I0 = ( | Π{0} (α) | es impar ) y P1 = ( | Π{1} (α) | es par ).
> Como no surge ninguna descomposición natural de esta conjunción en una disyunción se toma un sólo P1 ≡ P y se crea el correspondiente estado q1 que lo tiene como invariante, resultando: I = {P1} , F={I0, P1} K.

> Paso 2. Si I0 P1 se satisface para αa para α se satisface ¬ I0 P1 si a=0 y
> I0 ¬P1 si a=1. Resultando que hay agregar a I los predicados (¬I0 P1) y (I0 ¬P1) para las distintas posibilidades de a, los correspondientes estados, de los cuales sean invariantes y las transiciones correspondientes, o sea:

> q2 con invariante (¬I0 P1) ,
> q3 con ( I0 ¬P1) y
> δ(q2,, 0) = {q1}, δ(q3 , 1) = {q1}

> Extendiendo el razonamiento se obtiene que finalmente I estará integrado por todas las conjunciones aplicadas a las combinaciones de {P0,¬P0} con {P1,¬P1}, a cada una las cuales hay que asociar un estado, resultando pues conveniente definir

> K = {I0,¬I0} X {P1,¬P1} (si qi = (R,S) su invariante Pi resulta R S) y
> δ ((R, S), 0) = {(¬R,S)}, δ((R,S), 1) = {(R,¬S)}

> Paso 3. Construcción del estado inicial. Como tanto la cantidad de ceros como la de unos de la cadena vacía es cero y por lo tanto par, resulta que λ satisface (¬I0 P1) ε I.

> Además (¬I0 P1) es el único predicado que es satisfecho por la cadena vacía y es invariante de Q3, por lo cual se toma Q3 como estado inicial.
> Con esto finaliza la construcción de M – figura siguiente- garantizándose que I por construcción constituya un cief para M = <Σ, K, δ, Q3, F> por lo queda demostrado también, que:

> L(M) = {α/ Po(α)} = {α / I0 P1} = L.

> Ejemplo 2:

> Construir un autómata finito determinista que acepte las cadenas decimales que representan números múltiplos de tres.

> Definiciones y propiedades del dominio que son usadas:

> Σ = {0,..9}, v: Σ → N / v(0)=0,..v(9)=9; val: Σ*→N / val(an .. a0) = Σ i=0..n v(ai).10i y val(λ) = 0.

> s ≡ 3 t sii mod(s,3) = mod(t,3); s+3 t = mod(s+t, 3);
> val(an .. a0) ≡ 3 v(an ) +3 . . +3 v(a0)

> El lenguaje buscado es L = {α/ mod(val(α), 3) = 0} = {α / val (α) ≡ 3 0 } = {α = an..a0 / v(ao) +3 .. +3v(an) = 0 } U {λ}.

> Este problema se resuelve siguiendo los pasos:

> Paso 1. Se comienza el análisis a partir de P = val (α) ≡ 3 0.
> No aparece ninguna manera razonable de descomponer P en una disyunción por lo cual se toma I = {P} y se crea un estado qo, del cual es invariante, qo que debe ser final, resultando I = {P}, F = {qo} K

> Paso 2. val (αa)≡3 0 entonces si a ≡3 0 resulta val (α)≡3 0.
> si a ≡3 1 resulta val (α)≡3 2
> si a ≡3 2 resulta val (α)≡3 1

> Resultando para α tres predicados, el primero de los cuales coincide con P.

> También resultan las correspondientes transiciones:

> P0 = P = val (α)≡3 0 δ(q0, 0)={q0 }
> P1 = val (α)≡3 1 δ(q1, 2)={q0 }
> P2 = val (α)≡3 2 δ(q2, 1)={q0 }

> Donde 0 = {0, 3, 6, 9}
> 1 = {1, 4, 7 }
> 2 = {2, 5, 8 }

> I se extiende a {P0, P1, P2}, K a {q0, q1 q2} siendo Pi el invariante de qi. No hace falta extender más, pues se verifica α a Pj ε I : (Pj(αa) Pi : Pi (α)) pero debe completarse δ para que, para cada Pj y cada Pi se verifique que (qi, a) * (qj, λ), por lo cual la función de transición δ queda definida como lo muestra la figura siguiente.

> Paso 3. Como está establecido que val(λ)=0 el estado inicial deberá ser q0, completándose la construcción de M.

Atrás Siguiente

##### Introducción / Contenido / Unidad I / Unidad II / Unidad III / Unidad IV / Unidad V / Unidad VI / Unidad VII / Unidad VIII / Unidad IX / Problemario / Bibliografía

##### Inicio

##### Créditos

José Sánchez Juárez, Andrés Ortigoza Campos, Fabiola Ocampo Botello