LyA
96 LyA La tabla de transición de la fig. 3.4 si cumple con
la regla : Letra n Dig = Ø Letra n Sub = Ø Dig n
Sub = Ø Ø es el conjunto vacío. Los pares p
( s , a ) representados en la tabla se listan enseguida: ( 0 ,
Letra ) ( 0 , Dig ) ( 0 , Sub ) 1 Error Error ( 1 , Letra ) ( 1 ,
Dig ) ( 1 , Sub ) 1 1 1 La tabla antes del mapeo de los pares p (
s , a ) a un estado t, estaba vacía, es decir : Simbolos
en la entrada Estados LyA En un AFD con columnas c1 , c2 , … ,
ck donde k es el número de posibles entradas, se debe
cumplir: cin cj = Ø , para i ? j Lo anterior es sumamente
importante, dado que si no se cumple cin cj = Ø
podríamos tener un autómata finito no
determinístico. ¿ De dónde salieron estos
pares ?
97 LyA Y … ¿ Cómo se llenan o instancian sus
entradas ? LyA Pues precisamente del diagrama del AFD de la fig.
3.3. Por ejemplo, el par ( 0 , Letra ) se puede leer : “Si
el estado es el 0, y la lectura en la entrada es una letra, el
autómata se moverá al estado 1”. O sea que :
move ( 0 , Letra ) = 1 Esta transición es representada por
el arco etiquetado por Letra, y que “sale” del estado
0 hacia el estado 1, en el diagrama del AFD. El resultado de la
función move ( s , a ) para un automata finito
detreminístico es un solo estado ó bien ninguno
(caso de error). move ( s,a ) = un solo estado. NINGÚN
ESTADO equivale a un error. LyA ……………………… para
un AFD. Los move’s que producen error, son los pares: ( 0 ,
Dig ) y ( 0 , Sub ). move ( 0 , Dig ) = error, move ( 0 , Sub ) =
error, ya que en el AFD no hay arco que salga del estado 0 (cero)
y que sea etiquetado ya sea por Dig o por Sub. Bueno, pues ya
supe como llenar las casillas de la tabla de transición
del AFD.
98 El estado de inicio es el estado 0 y siempre se indica con un
arco llegando a dicho estado. Las características que
además debe cumplir el AFD son : a) No arcos ?. Si se
cumple, dado que no existe un solo arco etiquetado ? con en el
diagrama del AFD. b) De los estados 0 y 1, se observan
sólo arcos etiquetados en forma única. Nunca se
repite una etiqueta para dos o más arcos saliendo de un
estado. Existe un algoritmo para simular el funcionamiento de un
AFD, al efectuar el reconocimiento o rechazo de una cadena. Fig.
3.5. Utilicemos el algoritmo de la fig. 3.5 para reconocer la
cadena iCont1 con el AFD del ejemplo 3.1. La ejecución
paso a paso se muestra en la tabla de la fig. 3.6, donde las
columnas son variables y sus valores se indican, de acuerdo a la
instrucción que se ejecuta en secuencia. LyA 4. s 0 = 0
Estado de inicio del AFD. Sólo tenemos un estado de
aceptación y es el denotado con doble círculo : 1.
Así, el quinto componente F es: F = {1} La notación
de conjuntos es debido precisamente a que F es un conjunto.
LyA
99 Entrada Cadena x terminada en el caracter eof. D
(autómata AFD) con estado de inicio s0 y F conjunto de
estados finales. Proceso s = s0 c = NextChar ( ) while ( c ? eof
) do s = move ( s , c ) c = NextChar ( ) endwhile if ( s
está en F ) then return ‘si’ else return
‘no’ Salida Respuesta ‘si’ si D acepta a
x, de otra manera la respuesta es ‘no’. Fig. 3.5.
Carta EPS, del algoritmo que simula a un AFD. Fig. 3.6.
Reconocimiento de la cadena iCont1. La función NextChar( )
retorna el siguiente caracter de la cadena de entrada x.
100 El estado de inicio es : s0 = 0, LyA De la tabla fig. 3.6
podemos ver que : move ( 0 , i ) = 1 move ( 1 , C ) = 1 move ( 1
, o ) = 1 move ( 1 , n ) = 1 Dado que s = 1, entonces si
pertenece a F, por lo tanto el algoritmo retorna un
“si”. El AFD acepta la cadena : iCont ¿
Cómo son obtenidos estos move’s ? 0 1 Letra Inicio 2
4 3 move ( 1 , t ) = 1 move ( 1 , 1 ) = 1 De la tabla de
transición del AFD Fig. 3.4. Por ejemplo el move ( 0 , i )
= 1, se lee : “si el autómata se encuentra en el
estado 0 y llega una letra -en este caso la i-, el
autómata pasa al estado 1. El move ( 1 , 1 ) = 1, se busca
en el renglón cuyo estado es 1 y la columna Dig
(dígito). Ejemplo 3.2. Existe otro AFD para reconocer el
token id del ejemplo 3.1 que no es óptimo, ya que tiene
más estados y transiciones que el anterior. Letra Sub
Letra Dig Sub Letra Dig Dig Dig Sub Letra Sub Fig. 3.7 AFD para
el token id, con 5 estados.
101 Los estados de aceptación son 4 : El alfabeto es el
mismo, es decir : F = { 1, 2, 3, 4 } ? = { A, B, … , Z, a, b,
… , z, 0, 1, … , 9 , _ } El conjunto de estados S del AFD,
tiene 5 elementos : S = { 0, 1, 2, 3, 4 } La tabla de
transición -función move- tiene 5 renglones (todos
los estados, tienen al menos un arco saliendo de ellos) y 3
columnas : Símbolos en la entrada Estados En la fig. 3.8
se muestra el trazo del algoritmo que simula al AFD, en el
reconocimiento de la cadena X11A_2.
102 3.3 AUTÓMATA FINITO NO DETERMINÍSTICO (AFND).
Un autómata finito no determinístico es un modelo
matemático que consiste de : 1. Un conjunto de estados, S.
2. Un conjunto de símbolos de entrada, ? (alfabeto). 3.
Una función de transición denominada move, que
mapea pares, p ( s , a ) hacia un conjunto de estados. s es un
estado y a es un símbolo en la entrada. 4. Un estado de
inicio denotado por s0. 5. Un conjunto de estados de
aceptación, denotado por F. LyA Fig. 3.8.
Simulación del AFD con F = { 1, 2, 3, 4 } Ya que s = 3 y s
pertenece a F, el AFD retorna un ………………..
“si”
103 ….. LyA 1 2 3 ? b a Fig. 3.9 AFND para a + b + En la Fig.
3.9 se muestra el AFND para la expresión regular a+b+.La
función move (1 ,a) se define como : move ( 1 , a ) = { 1
, 2 } y move ( 2 , b ) = { 2 , 3 } ¿Hay dos estados a
donde el autómata puede efectuar una transición ?
Además, un AFND tiene como característica que lo
diferencia de un AFD, permitir el uso de arcos etiquetados por el
símbolo ?. ? Arcos ? La característica de donde
toma el nombre un AFND, consiste en que su función de
transición move, mapea los pares p ( s , a ) hacia un
conjunto de estados. Revisa el punto 3 para un AFD y vas a
encontrar que el autómata determinístico, mapea los
pares p(s,a) …. a un sólo estado. !!!! LyA ¿
Qué significa lo anterior ?. Significa que un AFND que se
encuentra en un estado s y para un símbolo en la entrada
a, pueden existir más de un arcos etiquetados con el
símbolo a saliendo del estado s, Fig.3.9. Por lo tanto no
está determinada la transición. 1 2 3 a b a b
104 Los componentes del AFND de la Fig. 3.9 son : El conjunto de
estados S = { 1, 2, 3 }, estado inicial s0 = 1 y sólo hay
un estado de aceptación F = { 3 }. El alfabeto de entrada
es ? = { a, b }. S, s0, F y ? son obtenidos directamente del
diagrama que representa el AFND. La tabla de transición es
: Símbolos en la entrada Estados move ( 1 , a ) = { 1 , 2
} move ( 1 , b ) = Error move ( 2 , a ) = Error move ( 2, b) = {
2 , 3} Podemos apreciar que el estado 3 no se incluyó en
los renglones de estados, ya que no existen arcos que
“salgan” de él, o sea, move ( 3 , a ) = Error
y move ( 3 , b ) = Error. Ejemplo 3.3 Veamos el correspondiente
AFND para el token id en Pascal, de los ejemplos 3.1 y 3.2. Los
componentes del AFND son : 0 1 2 LyA Letra En ambos casos la
función move nos mapea a 2 estados ¿ A qué
estado el autómata efectúa la transición ?
¡ No está determinado ! Por esta razón es un
autómata finito no determinístico (AFND). ? Letra |
Dig | Sub inicio
Autómatas Finitos 105 S s0 ? F Ing. Fco. Ríos
Acosta = { 1, 2, 3 } = 0 = { A, B, … , Z, a, b, … , z, 0, 1,
… , 9 , _, ? } = {2} La función de transición
move : Símbolos en la entrada Letra Dig Sub ? Estados 0
{1} – – – 1 {1} {1} {1} {2} Se ha incluído el
símbolo ? en la tabla de transición, debido a la
característica del AFND que permite arcos -transiciones-
etiquetadas por ?. No podemos utilizar el algoritmo de la fig.
3.5 para simular el AFND, pero si podemos efectuar el trazo de la
función move cuando se reconoce una cadena. Por ejemplo,
si la cadena es iCont, tenemos lo siguiente : i C o n t ? 0 1 1 1
1 1 2 3.4 AUTÓMATAS FINITOS Y EXPRESIONES REGULARES.
Existen algoritmos que relacionan la especificación de
tokens -expresiones regulares-, con el reconocimiento de
éstos -autómatas finitos-. Es posible dada una
expresión regular obtener el AFD que reconozca las cadenas
del lenguaje denotado por la expresión regular.
También es posible obtener el AFND que reconozca el
lenguaje representado por dicha expresión regular.
“si” acepta la cadena iCont LyA Observa que para este
ejemplo, el mapeo de los pares p(s,a) es siempre hacia un
sólo estado. En este caso si está determinada la
transición, pero el autómata es no
determinístico, debido al arco ? del estado 1 al estado
2.
106 El algoritmo que permite construir el autómata finito
determinístico está fuera del alcance de estas
notas ( el alumno no tiene los prerequisitos para su estudio en
este curso). Sin embargo, el algoritmo utilizado para la
construcción del autómata finito no
determinístico AFND, es relativamente sencillo de aplicar,
ya que se basa en reglas simples. Existen muchas variantes de
este algoritmo denominado “Algoritmo de Thompson”.
Este algoritmo es dirigido por sintáxis, es decir, usa la
estructura sintáctica de la expresión regular para
guiar el proceso de construcción del autómata AFND.
En la Fig 3.10 se muestra la carta Entrada-Proceso-Salida (EPS)
para el algoritmo de construcción de Thompson. Entrada
Expresión regular r definida sobre un alfabeto ?. Proceso
Primero, reconocemos las subexpresiones que constituyen a r.
Usando las reglas (1) y (2), construímos los AFND’s
para cada símbolo básico en r. Guiados por la
estructura sintáctica de la expresión regular r,
combinamos estos AFND´s de manera inductiva usando la regla
(3) hasta obtener el AFND para la expresión regular r.
Salida Un AFND que reconoce al lenguaje L ( r ). Fig. 3.10 Carta
EPS para el algoritmo de construcción de Thompson. Las
reglas a las que hace mención el algoritmo de Thompson son
las siguientes : 1. Para el símbolo ?, construir el AFND :
i es el nuevo estado inicial, y f es el nuevo estado de
aceptación. Este AFND reconoce a { ? }. f i inicio ?
ALGORITMO DE THOMPSON Expresión Regular Autómata
finito no determinístico (AFND)
107 ? ? ? ? De nuevo, i es el nuevo estado inicial, y f es el
nuevo estado de aceptación. Este autómata reconoce
{ a }. 3. Supongamos que N(s) y N(t) son AFND’s para las
expresiones regulares s y t, respectivamente. a) Para la
expresión regular s | t (alternancia), construir el
siguiente AFND, N(s|t) : i es el nuevo estado inicial, y f es el
nuevo estado de aceptación. Se añade una
transición ? desde i hacia los estados de inicio de N(s) y
de N(t). Además, se añade una transición ?
desde los estados de aceptación N(s) y de N(t) hacia el
nuevo estado de aceptación f. Los estados de inicio y de
aceptación de N(s) y de N(t) no son los estados de inicio
y de aceptación del autómata N(s|t). Este AFND
reconoce, L(s) U L(t). b) Para la expresión regular st
(concatenación), construir el AFND, N(st) : f i i inicio
inicio 2. Para cualesquier símbolo a del alfabeto ?,
construir el AFND : a N(s) N(t) i inicio f N(s) N(t) f
108 Ejemplo 3.4. Dada la expresión regular Token (c|d*)a
construir su correspondiente AFND. La descomposición
sintáctica de la expresión regular consiste de 6
etapas básicamente: c d d* c|d* a (c|d*)a i inicio El
estado de inicio de N(s) es ahora el estado de inicio para el
AFND N(st), y el estado de aceptación de N(t) se vuelve el
estado de aceptación del AFND, N(st). El estado de
aceptación de N(s) es mezclado con el estado inicial de
N(t); esto significa que todas las transiciones, desde el estado
inicio de N(t) son ahora arcos o transiciones desde el estado de
aceptación de N(s). El nuevo estado que resulta de esta
mezcla, pierde su estatus de estado de inicio o aceptación
para el nuevo AFND. El AFND así construido, reconoce el
lenguaje L(s) L(t). c) Para la expresión regular s*,
construir el AFND, N(s*) : ? f ? i es un nuevo estado inicial, y
f es un nuevo estado de aceptación. Con el nuevo AFND se
reconoce el lenguaje ( L(s) ) *. ? ? N(s) LyA Orden de
aplicación de las reglas. Construiremos 4 AFND’s
para cada una de las etapas, hasta llegar al AFND que reconoce :
Token AFND para el símbolo c, regla 2 : (c|d*)a
109 Autómatas Finitos AFND para d*. Primero obtenemos el
AFND para el símbolo d (regla 2) : Ahora podemos encontrar
la tercera etapa, es decir, c | d * , la alternancia del
símbolo c con la cerradura de d : ? ? ? ? ? 4 4 inicio ? ?
? ? ? Luego, seguimos con la construcción del AFND para d*
(regla 3c) : ? d d 3 5 3 5 2 2 6 Ing. Fco. Ríos Acosta c
inicio 1 0 2 inicio 3 d inicio 0 1 c 7 AFND para d * LyA ? Regla
3 a). c|d*
? ? 110 Por último, aplicaremos la regla 3b, para
concatenar el AFND para c|d* con el AFND del símbolo a: Es
buena costumbre, reenumerar los estados en orden progresivo
ascendente. De acuerdo a ésto, el AFND que reconoce a la
expresión regular Token (c | d*) a es : ( 3.4.1 ) a ? ? ?
? 4 ? ? ? d 3 5 2 6 inicio 0 1 AFND para a c 9 7y8 8 inicio 9 a a
? ? ? ? 3 ? ? ? d 5 6 4 0 inicio 1 2 c 7 8 ? LyA ? Los estados 7
y 8 se unieron para formar uno sólo. Tienes que ponerle un
número de estado único. !!!
111 Cualquier AFND construido con el Algoritmo de Thompson, tiene
como característica que existe sólo un estado de
inicio y sólo un estado de aceptación.
Además, del estado de aceptación nunca
“sale” o existe una transición. Los
componentes para el AFND que reconoce ( c | d* ) a son : s0 F S ?
= = = = 0 ; estado inicial. { 8 } ; estado de aceptación.
{ 0, 1, 2, 3, 4, 5, 6, 7, 8 } ; conjunto de estados que forman el
AFND. { ?, c, d, a } Función de transición move( s
, a ) : Símbolos en la entrada Estados Ejemplo 3.5. Dada
la expresión regular : Letra Dig Sub Id ? ? ? ?
A|B|…|Z|a|b|…|z 0|1|…|9 _ (Letra ) ( Letra | Dig | Sub ) *
Construir el AFND correspondiente. Iniciemos observando, que la
expresión regular Id consiste de la concatenación
de la expresión regular Letra, con la cerradura de una
alternancia de las 3 expresiones regulares : Letra, Dig y
Sub.
112 La descomposición sintáctica es la siguiente :
Letra Dig Sub Letra | Dig Letra | Dig | Sub ( Letra | Dig | Sub )
* El AFND para letra es construido dos veces, en forma separada.
En lo anterior hace hincapié el algoritmo de Thompson. Se
construye dos veces, dado que la expresión regular Letra
aparece en dos operaciones : La misma regla 2 es aplicada para
obtener el AFND para las expresiones regulares Dig y Sub : 4
inicio 5 Dig ( 3.5.3 ) 0 inicio 1 ( Letra ) ( Letra | Dig | Sub )
* El AFND para letra es construido con la regla 2 : Letra 2 3
Así pues, obtengamos el otro AFND para la expresión
regular Letra. Letra inicio LyA Tenemos que construir 7
autómatas para encontrar el AFND deseado. ( 3.5.1 ) LyA
Concatenación y la alternancia ( Letra ) ( Letra | Dig |
Sub ) * ( 3.5.2 )
113 Autómatas Finitos Apliquemos ahora la regla 3 c) al
AFND 3.5.6, y encontraremos la cerradura ( Letra | Dig | Sub ) *
: 6 7 Ing. Fco. Ríos Acosta Sub inicio ( 3.5.4 ) ? ? ? 4 5
? Dig 2 3 La regla 3a) se aplica sobre los AFND’s 3.5.2 y
3.5.3 para obtener Letra | Dig : Letra 8 inicio 9 ( 3.5.5 ) ?
inicio ? ? ? ? ? ? ? 4 5 Dig 2 3 El AFND para Letra | Dig | Sub
es encontrado con la regla 3 a) y los autómatas (3.5.4) y
(3.5.5) : Letra 8 9 6 7 Sub 11 10 ( 3.5.6 ) 12 inicio ? ? ? ? 13
? ? ? ? ? 4 5 Dig 2 3 Letra 8 9 ? 6 7 Sub ? 11 ? 10 ( 3.5.7 )
114 Los componentes del AFND construido mediante el algoritmo de
Thompson : s0 S ? F = = = = 0 { 0,1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
11, 12 } { A, B, … , Z, a, b, … , z, 0, 1, … , 9 , _ } { 12
} Función move (s,a) : ( 3.5.8 ) Letra ? ? Sólo
hace falta encontrar la concatenación de Letra con
(Letra|Dig|Sub)*. Los AFND’s involucrados son el 3.5.1 y
3.5.7. Los estados 1 y 12 se mezclan regla 3 b). ? Letra 13 ? ? ?
? ? 4 5 Dig 2 3 8 9 ? 6 7 Sub ? 11 ? 10 0 inicio 10 1 Letra ? ? ?
12 ? ? ? ? ? 6 7 Dig 4 5 1 y 12 ? Es recomendable reenumerar los
estados del AFND. ? Letra 3 8 ? 9 Sub ? 11 ? 2 0 inicio
Dig Dig . 115 Autómatas Finitos LyA Ing. Fco. Ríos
Acosta Símbolos en la entrada Estados Ejemplo 3.6.
Construir el AFND que reconoce la definición regular : Dig
NumEsp 0 | 1 | … | 9 Dig+.Dig+ NumEsp es una expresión
regular que denota al lenguaje formado por las cadenas que son
números con punto decimal y al menos una cifra entera y
una cifra en la fracción. La descomposición
sintáctica de la expresión regular NumEsp, es una
concatenación de 3 subexpresiones regulares : Dig+ •
+ // Cerradura positiva de Dig // Caracter punto // Cerradura
positiva de Dig Tenemos que construir 7 autómatas para
llegar a la solución : Dig Dig+ . + Dig Dig+ Dig+ . Dig+
Pero sabemos que : r+ = r r* Y … ¿ Cómo encuentro
Dig + ? ¡¡ No existe regla !!
116 Por lo tanto, podemos descomponer Dig+ en : Dig + = Dig Dig *
Así, los AFND’s que debemos obtener son los
siguientes : Dig Dig * Dig Dig * // Dig + . Dig Dig * . Dig . 5 6
La regla 3 b es para DigDig* . Los estados 4 y 5 se mezclan al
efectuar la concatenación : AFND para el símbolo
“.” LyA Orden de construcción de los
AFND’s. Dig Dig 1 ? Dig * Dig Dig * // Dig + Dig Dig * .
Dig Dig * Aplicando reglas 2, 3 c) y 3 b), tenemos el AFND para
Dig+ : ? ? 3 4 2 0 inicio Dig ? Dig* ( 3.6.1 ) = Dig+
 Página anterior | Volver al principio del trabajo | Página siguiente  |