UNIDAD 3.- AUTOMATAS FINITOS.
3.1 CONCEPTO DEFINICIÓN Y CLASIFICACIÓN DE
AUTÓMATA FINITO (AF)
Un
autómata finito (AF) o máquina de estado finito es un modelo computacional que
realiza cómputos en forma automática sobre una entrada para producir una
salida.
Este
modelo está conformado por un alfabeto, un conjunto de estados y un conjunto de
transiciones entre dichos estados. Su funcionamiento se basa en una función de
transición, que recibe a partir de un estado inicial una cadena de caracteres
pertenecientes al alfabeto (la entrada), y que va leyendo dicha cadena a medida
que el autómata se desplaza de un estado a otro, para finalmente detenerse en
un estado final o de aceptación, que representa la salida.
La
finalidad de los autómatas finitos es la de reconocer lenguajes regulares, que
corresponden a los lenguajes formales más simples según la Jerarquía de
Chomsky.
Definición
formal Formalmente:
E: alfabeto de entrada.
Q: conjunto de estados; es conjunto finito no vacío.
f: función de transición. f(p,a)=q
q0 : (perteneciente a Q) estado inicial.
F : (perteneciente a Q) conjunto de estados finales o de aceptación.
Q: conjunto de estados; es conjunto finito no vacío.
f: función de transición. f(p,a)=q
q0 : (perteneciente a Q) estado inicial.
F : (perteneciente a Q) conjunto de estados finales o de aceptación.
En el
comienzo del proceso de reconocimiento de una cadena de entrada, el autómata
finito se encuentra en el estado inicial y a medida que procesa cada símbolo de
la cadena va cambiando de estado de acuerdo a lo determinado por la función de
transición.
Cuando se ha procesado el último de los símbolos de la cadena de
entrada, el autómata se detiene en el estado final del proceso. Si el estado
final en el que se detuvo es un estado de aceptación, entonces la cadena
pertenece al lenguaje reconocido por el autómata; en caso contrario, la cadena
no pertenece a dicho lenguaje.
Note
que el estado inicial de un autómata finito siempre es único, en tanto que los
estados finales pueden ser más de uno, es decir, el conjunto puede contener más
de un elemento. También puede darse el caso de que un estado final corresponda
al mismo estado inicial.
CLASIFICACIÓN DE AF LOS AUTÓMATAS SE PUEDEN
CLASIFICAR EN:
· Deterministas; Cada
combinación (estado, símbolo de entrada) produce un solo estado.
· No Deterministas; Cada
combinación (estado, símbolo de entrada) produce varios estados y además son
posibles las transiciones con λ.
Los autómatas se pueden
representar mediante tablas de transición o diagramas de transición.
REPRESENTACION:
TABLA |
a
|
b
|
->p
|
q
|
|
*q
|
q3
|
r
|
q3
|
r
|
|
r
|
q3
|
Tablas de transición:
• Filas encabezadas por los estados( Q )
• Columnas encabezadas por los símbolos de entrada ( E )
Diagramas
de transición:
• Nodos etiquetados por los estados(Q)
• Arcos entre nodos etiquetados con ( E )
• Q0 se señala con ->
• El estado final se señala con * o con doble circulo
• Arcos entre nodos etiquetados con ( E )
• Q0 se señala con ->
• El estado final se señala con * o con doble circulo
Ejemplo: Sea el AFD1 = ({a,b}, {p,q,r}, f, p, {q}) donde f está
definida por:
f(p,a) = q f(p,b) = r
f(q,a) = q f(q,b) = r
f(r,a) = r f(r,b) = r
f(p,a) = q f(p,b) = r
f(q,a) = q f(q,b) = r
f(r,a) = r f(r,b) = r
Escribir su tabla de transición y dibujar su diagrama de transición.
estados (Q): p, q, r
estado inicial: p
estado final: q
Bibliografia:
Enrique Alfonseca Cubero, Manuel Alfonseca Cubero, Roberto Moriyón Salomón." Teoría de autómatas y lenguajes formales". McGraw-Hill (2007). Capítulos 3 y 7
Maigualida
Pérez Melgarejo
3.2 CONVERSIÓN DE AUTÓMATA FINITO NO DETERMINISTA A AUTÓMATA FINITO DETERMINISTA.
3.2 CONVERSIÓN DE AUTÓMATA FINITO NO DETERMINISTA A AUTÓMATA FINITO DETERMINISTA.
Todo AFND estricto, puede ser
transformado a AFD utilizando un
algoritmo que transforma los estados del AFND en nuevos estados que son
subconjuntos de los estados originales y aplica a los mismos la clausura para
confirmar la conexidad entre cada uno de los componentes y así eliminar el
indeterminismo.
Sea un autómata
finito estrictamente no determinista (AFND) definido por la
5-tupla A=<Q, T, g, F, q0>, donde Q es
el conjunto de estados, T el alfabeto de símbolos terminales, la relación de transiciones
1. A se transforma
en AAFD=<QA,T, gA,FA,q0A>',
tal que:
b. FA={x | }.
c. gA={<r,x,q>
| }.
d. q0A={q0}
2.
Luego se eliminan de AAFD todos
los estados y sus correspondientes transiciones inalcanzables desde el estado
inicial q0A.
Ejemplo
Véase el proceso de transformación de AFND a AFD del autómata A=<{q0,q1,f},{a,b},{<q0,a,q0>,<q0,b,q0>,<q0,a,q1>,<q1,b,f>},{f},q0>,
que reconoce a las cadenas de as y bs que comienzan con
cualquiera cantidad de estas letras y terminan forzosamente en ab.
Primero
se obtiene autómata derivado AAFD=<VAFD,TAFD,gAFD,FAFD,{q0}> a
partir del conjunto potencia de los estados de A donde:
·
VAFD={{q0},{q1},{f},{q0,q1},{q0,f},{q1,f},
{q0,q1,f}}.
·
TAFD={a,b}.
·
FAFD={{f},{q0,f},{q1,f}, {q0,q1,f}}.
Luego se
retiran los estados inaccesibles {q1}, {f}, {q1,f}, {q0,q1,f},
determinados mediante la clausura de {q0}, y queda:
·
AAFD={{q0,{q0,q1},{q0,f}},{a,b},{<{q0},b,{q0}>,<{q0},a,{q0,q1}>,<{q0,q1},a,{q0,q1}>,<{q0,q1},b,{q0,f}>,<{q0,f},a,{q0,q1}>,<{q0,f},b,{q0}>},{
{q0,f} },{q0}}.
Blanca Estela Reyes Castillo
3.3 REPRESENTACIÓN DE ER USANDO AFND.
ERs, AFDs y AFNDs son mecanismos equivalentes para denotar los lenguajes regulares. En estas tres secciones demostraremos esto mediante convertir ER→AFND → AFD → ER. Las dos primeras conversiones son muy relevantes en la práctica, pues permiten construirverificadores o buscadores eficientes a partir de ERs.
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. El algoritmo que permite construir el autómata finito
determinístico está fuera del alcance de estas notas (el alumno no
tiene los prerrequisitos 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
sintaxis, es decir, usa la estructura sintáctica de la expresión regular para
guiar el proceso de construcción del autómata AFND. Supongamos
que N(s)y N(t)son AFND’s para las expresiones regulares sy t,
respectivamente.
a) Para la expresión regular s | t(alternancia), construir el siguiente AFND, N(s|t):
b) Para la expresión regular st(concatenación), construir el AFND, N(st) :c)
c) Para la expresión regular s*, construir el AFND, N(s*) :
bibliografia
https://www.scribd.com/doc/226694899/Unidad-III-y-IV-Lenguajes-y-Automatas-i
3.4
MINIMIZACION DE ESTADOS EN UN AF.
Dos
estados de un autómata finito determinista son estados equivalentes si al
unirse en un sólo estado, pueden reconocer el mismo lenguaje regular que si
estuviesen separados. Esta unión de estados implica la unión tanto de sus
transiciones de entrada como de salida. Si dos estados no son equivalentes, se
dice que son estados distinguibles. Un estado final con un estado no-final
nunca serán equivalentes.
Un AFD
está minimizado, si todos sus estados son distinguibles y alcanzables. Un
algoritmo de minimización de AFD es el siguiente:
Eliminar
los estados inaccesibles del autómata.
Construir
una tabla con todos los pares (p, q) de estados restantes.
Marcar
en la tabla aquellas entradas donde un estado es final y el otro es no-final,
es decir, aquellos pares de estados que son claramente distinguibles.
Para
cada par (p, q) y cada símbolo a del alfabeto, tal que r = δ(p,a) y s = δ(q,a):
Si (r,
s) ya ha sido marcado, entonces p y q también son distinguibles, por lo tanto,
marcar la entrada (p, q).
De lo
contrario, colocar (p, q) en una lista asociada a la entrada (r, s).
Agrupar
los pares de estados no marcados.
Luego
del tercer paso, si la tabla creada queda completamente marcada, entonces el
AFD inicial ya era mínimo.
finalmente
se obtiene el autómata final, agrupando los estados b y f, así como c y g.
Ejemplo:
Dado un AFD M = (Q, Σ, δ, q0, F), se trata de encontrar un AFD M′ con
L(M) = L(M′) y tal que M′ tenga el mínimo numero de estados posible. Para ello,
el método consiste en encontrar todos los estados que son equivalentes, es
decir, que son indistinguibles en el autómata. Por cada clase de estados
equivalentes, el autómata mínimo necesitara un solo estado.
Dados
dos estados q, q′ ∈ Q, q
y q ′ son indistinguibles o equivalentes si para cualquier cadena w ∈ Σ ∗ se cumple una de las dos
siguientes opciones:
·
δ(q, w) ∈ F y δ(q
′ , w) ∈ F
·
δ(q, w) 6∈ F y δ(q
′ , w) ∈ F 1
El método
para minimizar un autómata consiste básicamente en encontrar todos los estados
que son indistinguibles entre si y sustituirlos por un único estado. Para ello
lo principal es averiguar que estados son distinguibles y cuales no.
El método
para saber que estados son indistinguibles es el siguiente:
a. Si
hay algún estado inalcanzable eliminarlo
b. (i
:= 0) Marcar todos los estados que pueden distinguirse con la cadena
vacía
(es decir, todos los finales se pueden distinguir de los no finales).
c. (i
:= i + 1) Marcar como distinguibles q y q′
si con
algún a ∈ Σ tenemos δ(q, a) y δ(q′, a)
dos estados que ahora son distinguibles.
d. Si
en el paso anterior se han distinguido nuevos estados, entonces volver
al
paso c.
Bibliografia:
John E. Hopcroft, Rajeev Motwani, Jeffrey
D.Ullman. "Introducción a la teoría de autómatas, lenguajes y
computación" (3ª edición). Ed, Pearson Addison Wesley.
Sects. 2.1-2.2; Sects. 2.3-2.8; HMU, Chap.
4;HMU, Sects. 3-1-3.7
Edgarda Santiago Reyes
3.5 APLICACIONES (DEFINICIÓN DE UN CASO DE
ESTUDIO)
•
Interruptor de luz
•
Control de máquinas de bebidas
•
Analizadores/generadores de palabras
•
Control de las tareas de un robot
•
Búsqueda y sustitución de palabras
•
Tratamiento de masas de textos
•
Analizadores léxicos de compiladores y traductores
• etc.
Máquina de bebidas:
1. Las
bebidas cuestan 25 céntimos.
2.
Monedas que admite la máquina:
1. De
cuarto, 25 céntimos (Q).
2.
Dimea, 10 céntimos (D).
3.
Nickel, 5 céntimos (N).
3. La
máquina acepta cualquier combinación
de
monedas hasta 25 céntimos.
4. La
máquina requiere la cantidad exacta.
Bibliografía:
Marisa Martínez Bautista
