| 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.7 Conversión de un AFN a AFD (Construcción de subconjuntos)

> La transformación de un AFD a un AFN se puede hacer por medio del algoritmo de subconjuntos.

> CONSTRUCCIÓN DE SUBCONJUNTOS

> Construcción de un AFD a partir de un AFN.

> ENTRADA. Un AFN.

> SALIDA. Un AFD que acepta el mismo lenguaje.

> MÉTODO. El algoritmo construye una tabla de transiciones traed para D, en donde cada estado del AFD es un conjunto de estados del AFN y se construye traed de modo que D simulara “en paralelo” todos los posibles movimientos que N puede realizar con una determinada cadena de entrada.

> Se utilizan las operaciones de la siguiente figura para localizar los conjuntos de los estados del AFN (s representa un estado del AFN, y T, un conjunto de estados del AFN).

OPERACIÓN | DESCRIPCION
Cerradura-€ (S) | Conjunto de estados del AFN alcanzables desde el estado s del AFN con transiciones € solamente.
Cerradura-€ (T) | Conjunto de estados del AFN alcanzables desde algún estado s en T con transiciones € solamente.
Mueve (T,a) | Conjunto de estados del AFN hacia los cuales hay una transición con el símbolo de entrada a desde algun estado s en T del AFN.

> Operaciones sobre los estados de un AFN.

> Antes de detectar el primer símbolo de entrada, N se puede encontrar en cualquiera de los estados del conjunto cerradura-€ (So), donde So es el estado de inicio de N. Supóngase que exactamente los estados el conjunto T son alcanzables desde So.

> Con una secuencia dada de símbolos de entrada, y sea a el siguiente símbolo de entrada. Al ver a, N puede trasladarse a cualquiera de los estados del conjunto mueve (T,a). Cuando se permiten transiciones -€, N puede encontrarse en cualquiera de los estados de cerradura-€ (T, a), después de ver la a.

> Al inicio, cerradura-€ (So) es el único estado dentro de estados D y no está marcado; while haya un estado no marcado T en estadosD do begin
> marcat T:
> for cada símbolo de entrada a do begin
> U: = cerradura-€ (mueve (T,a));
> If U no está en estadosD then
> Añadir U como estado no marcado a estadosD;
> tranD[T, a] : =U
> end
> end

> Construcción de subconjuntos

> Se construyen estados D, el conjunto de estados de D, y traed, la tabla de transiciones de D, de la siguiente forma, cada estado de D corresponde a un conjunto de estados de AFN en los que podría estar N después de leer alguna secuencia de símbolos de entrada, incluidas todas las posibles transacciones -€ anteriores o posteriores a la lectura de símbolos. El estado de inicio de D es cerradura -€(So), se añaden los estados y las transacciones a D utilizando el algoritmo anterior. Un estado de D es un estado de aceptación si es un conjunto de estados de AFN que contenga al menos un estado de aceptación de N.

> Meter todos los estados de T en pila:

> Inicializar cerradura -€ (T) a T;
> While pila no este vacía do begin
> Sacar t, el elemento del tope, de pila;
> For cada estado u con una arista desde t a u etiquetada con € do
> If u no está en cerradura -€ (T) do begin
> Añadir u a cerradura -€ (T);
> Meter u en pila
> End
> End

> Calculo de cerradura -€.

> El cálculo de cerradura -€ es un proceso típico de búsqueda en un grafo de nodos alcanzables desde un conjunto dado de nodos. En este caso, los estados de T son el conjunto dado de nodos, y el grafo está compuesto solamente por las aristas del AFN etiquetadas por €. Un algoritmo sencillo para calcular cerradura-€ (T) utilizada una estructura de datos tipo pila para guardar estados en cuyas aristas no se hayan buscado transiciones etiquetadas con €. Este procedimiento se muestra en el algoritmo anterior.

> Ejemplo:

> La figura que se muestra a continuación presenta otro AFN aceptando el lenguaje (a|b)*abb.

> Este se construirá mecánicamente a partir de la expresión regular, donde se aplica el algoritmo de construcción de subconjuntos al autómata AFN anterior. El estado de inicio del AFD equivalente es cerradura -€(0),que es A={0, 1, 2, 4, 7}, puesto que estos son exactamente los estados alcanzables desde el estado 0 por un camino en que todas las aristas están etiquetadas por €.

> Obsérvese que un camino puede no tener aristas, de modo que 0 es alcanzado desde si mismo por dicho camino.

> Aquí, el alfabeto de símbolos de entrada es {a, b}. El algoritmo de la construcción de subconjuntos indica que hay que marcar A y después calcular:

> Cerradura -€ (mueve(A,a)).

> Primero se calcula mueve(A,a), el conjunto de estados de N que tiene transiciones en a desde miembros de A. Entre los estados 0, 1, 2, 4 y 7 solo 7 tienen dichas transiciones, a 3 y a 8, de modo que:

> Cerradura -€ (mueve({0, 1, 2, 4, 7},a)) = cerradura-€ ({3,8}) = {1, 2, 3, 4, 6, 7, 8}

> Este conjunto se denominara B. Así, tranD[A, a] = B.

> Entre los estados de A, solo 4 tienen una transición en b a 5, de modo que el AFD tiene una transición en b desde A a

> C= cerradura-€({5})= {1,2,4,5,6,7}

> Por tanto, tranD[A,B] = C.

AFN que acepta (a|b)* abb

> Si se continúa este proceso con los conjuntos B y C, ahora sin marcar, finalmente se llegara al punto en que todos los conjuntos que son los estados del AFD estén marcados. Esto es cierto porque “sólo” hay 2 subconjuntos distintos de un conjunto d 11 estados, y un conjunto, una vez marcado, queda marcado para siempre.

> Los cinco conjuntos de estado diferentes realmente construidos son:

> A = {0,1, 2, 4, 7} D = {1, 2, 4, 5, 6, 7, 9}
> B = {1, 2, 3, 4, 6, 7, 8} E = {1, 2, 4, 5, 6, 7, 10}
> C = {1, 2, 4, 5, 6, 7}

> El estado A es el conjunto de inicio, y el estado E es el único estado de aceptación. La tabla de transiciones completa se muestra en la siguiente figura.

ESTADO | SIMBOLO DE ENTRADA
A | B
A | B | C
B | B | D
C | B | C
D | B | E
E | B | C

> Tabla de transiciones traed para el AFD.

> Además, en la siguiente figura se muestra un grafo de transiciones para el AFD resultante. También acepta (a|b)*abb y tiene un estado menos.

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