AUTOMATAS FINITOS DETERMINISTA
Descripción
del proyecto:
Definición
de autómata finito determinista Un autómata finito determinista consta
de:
1. Un conjunto finito de estados, a menudo designado como Q.
2. Un conjunto finito de símbolos de entrada, a menudo
designado como Σ.
3. Una función de
transición que toma como argumentos un estado y un símbolo de entrada y
devuelve un estado. La función de transición se designa habitualmente como δ.
En nuestra representación gráfica informal del autómata, δ se ha representa
mediante arcos entre los estados y las etiquetas sobre los arcos. Si q es un
estado y a es un símbolo de entrada, entonces δ(q,a) es el estado p tal que
existe un arco etiquetado a que va desde q hasta p. 2
4. Un estado inicial,
uno de los estados de Q.
5. Un conjunto de
estados finales o de aceptación F. El conjunto F es un subconjunto de Q. A
menudo haremos referencia a un autómata finito determinista mediante su
acrónimo: AFD. La representación más sucinta de un AFD consiste en un listado
de los cinco componentes anteriores. Normalmente, en las demostraciones,
definiremos un AFD utilizando la notación de “quíntupla” siguiente: A =
(Q,Σ,δ,q0,F) donde A es el nombre del AFD, Q es su conjunto de estados, Σ son
los símbolos de entrada, δ es la función de transición, q0 es el estado inicial
y F es el conjunto de estados finales.
Cómo procesa cadenas un AFD
primero que tenemos que entender sobre un AFD es cómo decide
si “aceptar” o no una secuencia de símbolos de entrada. El “lenguaje” del AFD
es el conjunto de todas las cadenas que acepta. Supongamos que a1a2 ···an es
una secuencia de símbolos de entrada. Comenzaremos con el AFD en el estado
inicial, q0. Consultamos la función de transición δ, por ejemplo δ(q0,a1) = q1
para hallar el estado al que pasará el AFD A después de procesar el primer
símbolo de entrada a1.
A continuación procesamos el siguiente símbolo de entrada,
a2, evaluando δ(q1,a2); supongamos que este estado es q2. Continuamos aplicando
el mismo procedimiento para hallar los estados q3,q4,...,qn tal que δ(qi−1,ai)
= qi para todo i. Si qn pertenece a F, entonces la entrada a1a2 ···an se acepta
y, si no lo es se “rechaza”.
EJEMPLO 2.1
Especificamos
formalmente un AFD que acepte únicamente todas las cadenas de ceros y unos que
contengan la secuencia 01 en cualquier posición de la cadena. Podemos describir
este lenguaje L como sigue: {w | w tiene la forma x 01y para algunas cadenas x
e y constan sólo de ceros y unos} Otra descripción equivalente que utiliza los
parámetros x e y a la izquierda de la barra vertical es: {x 01y | x e y son
cadenas cualesquiera formadas por 0s y 1s} Algunos ejemplos de cadenas de este
lenguaje son: 01, 11010 y 100011. Algunos ejemplos de cadenas que no pertenecen
a este lenguaje son: ε, 0 y 111000. ¿Qué sabemos sobre un autómata que puede
aceptar este lenguaje L? En primer lugar, sabemos que su alfabeto de entrada es
Σ = {0,1}. Tiene un determinado conjunto de estados, Q, siendo uno de ellos,
por ejemplo q0, el estado inicial. Este autómata tiene que recordar las entradas
que ha leído hasta el momento. Para decidir si 01 es una subcadena de la
entrada, A tiene que recordar: 1. ¿Ha leído ya una subcadena 01? En caso
afirmativo, aceptará cualquier secuencia de entradas futura; es decir, sólo se
encontrará en estados de aceptación. 2. ¿Todavía no ha leído la secuencia 01,
pero la entrada más reciente ha sido un 0, de manera que si ahora lee un 1,
habrá leído la subcadena 01 y podrá aceptar cualquier cosa que lea de ahí en
adelante? 3. ¿Todavía no ha leído la secuencia 01, pero la última entrada no
existe (acaba de iniciarse) o ha sido un 1? En este caso, A no puede aceptar la
entrada hasta que no lea un 0 seguido inmediatamente de un 1.
Cada una de estas tres condiciones puede representarse
mediante un estado. La condición (3) se representa mediante el estado inicial,
q0. Nada más comenzar seguramente necesitaremos leer un 0 seguido de un 1. Pero
si estando en el estado q0 lo primero que leemos es un 1, entonces no leeremos
la secuencia 01 y, por tanto, deberemos permanecer en el estado q0. Es decir,
δ(q0,1) = q0. Sin embargo, si estamos en el estado q0 y a continuación leemos
un 0, nos encontraremos en el caso de la condición (2). Es decir, nunca
leeremos la secuencia 01, pero tenemos un 0. Por tanto, utilizaremos q2 para representar
la condición (2). La transición de q0 para la entrada 0 es δ(q0,0) = q2.
Consideremos ahora las transiciones desde el estado q2. Si leemos un 0, no
mejoramos nuestra situación pero tampoco la empeoramos. No hemos leído la
secuencia 01, pero 0 ha sido el último símbolo, por lo que quedamos a la espera
de un 1. El estado q2 describe esta situación perfectamente, por lo que
deseamos que δ(q2,0) = q2. Si nos encontramos en el estado q2 y leemos una
entrada 1, entonces disponemos de un 0 seguido de un 1. Ahora podemos pasar a
un estado de aceptación, que denominaremos q1, y que se corresponde con la
condición (1). Es decir, δ(q2,1) = q1. Por último, tenemos que diseñar las
transiciones para el estado q1. En este estado, ya hemos leido una secuencia
01, así que, independientemente de lo que ocurra, nos encontraremos en una
situación en la que hemos leído la secuencia 01. Es decir, δ(q1,0) = δ(q1,1) =
q1. Por tanto, Q = {q0,q1,q2}. Como hemos dicho, q0 es el estado inicial y el
único estado de aceptación es q1; es decir, F = {q1}. La especificación
completa del autómata A que acepta el lenguaje L de cadenas que contienen una
subcadena 01 es A = ({q0,q1,q2},{0,1},δ,q0,{q1}) donde δ es la función de
transición descrita anteriormente.
Notaciones más
simples para los AFD Especificar un AFD utilizando una quíntupla con una
descripción detallada de la función de transición δ resulta bastante tedioso y
complicado de leer. Hay disponibles dos notaciones más cómodas para describir
los autómatas: 1. Un diagrama de transiciones, que es un grafo como los que hemos
visto en la Sección Una tabla de transiciones, que es una ordenación tabular de
la función δ, la cual especifica el conjunto de estados y el alfabeto de
entrada. Diagramas de transiciones Un diagrama de transiciones de un AFD A =
(Q,Σ,δ,q0,F) es un grafo definido como sigue: a) Para cada estado de Q, existe
un nodo. b) Para cada estado q de Q y cada símbolo de entrada a de Σ, sea
δ(q,a) = p. Entonces, el diagrama de transiciones tiene un arco desde el nodo q
hasta el nodo p, etiquetado como a. Si existen varios símbolos de entrada que
dan lugar a transiciones desde q hasta p, entonces el diagrama de transiciones
puede tener un único arco etiquetado con la lista de estos símbolos. c) Existe
un flecha dirigida al estado inicial q0, etiquetada como Inicio. Esta flecha no
tiene origen en ningún nodo. d) Los nodos correspondientes a los estados de
aceptación (los que pertenecen a F) están marcados con un doble círculo. Los
estados que no pertenecen a F tienen un círculo simple. EJEMPLO 2.2 La Figura
2.4 muestra el diagrama de transiciones del AFD que hemos diseñado en el
Ejemplo 2.1. En este diagrama podemos ver los tres nodos correspondientes a los
tres estados. Hay una flecha etiquetada como Inicio que entra en el estado
inicial, q0, y un estado de aceptación, q1, representado mediante un doble
círculo. De cada estado sale un arco etiquetado con 0 y otro con 1 (aunque los
dos arcos se han combinado en uno con una doble etiqueta en el caso de q1).
Cada uno de los arcos corresponde a una de las situaciones de δ desarrolladas
en el Ejemplo 2.1. Tablas de
transiciones Una tabla de transiciones es una representación tabular
convencional de una función, como por ejemplo δ, que toma dos argumentos y
devuelve un valor. Las filas de la tabla corresponden a los estados y las
columnas a las entradas. La entrada para la fila correspondiente al estado q y
la columna correspondiente a la entrada a es el estado δ(q,a).
Figura 2.4. Diagrama de transiciones del AFD que acepta
todas las cadenas que contienen la subcadena 01.
EJEMPLO 2.3 La tabla de transiciones correspondiente a la
función δ del Ejemplo 2.1 se muestra en la Figura 2.5. También pueden verse
otras dos características de una tabla de transiciones. El estado inicial se marca
mediante una flecha y los estados de aceptación mediante un asterisco. Dado que
es posible deducir los conjuntos de estados y los símbolos de entrada fijándose
en los encabezamientos de las filas y las columnas, podemos obtener a partir de
la tabla de transiciones toda la información necesaria para especificar el
autómata finito de forma unívoca.
Extensión a cadenas de la función de transición Hemos
explicado informalmente que el AFD define un lenguaje: el conjunto de todas las
cadenas que dan lugar a una secuencia de transiciones desde el estado inicial
hasta un estado de aceptación. En términos del diagrama de transiciones, el
lenguaje de un AFD es el conjunto de etiquetas ubicadas a lo largo de todos los
caminos que van desde el estado inicial hasta cualquier estado de aceptación.
Ahora es necesario precisar la notación del lenguaje de un AFD. Para ello,
definimos una función de transición extendida que describirá lo que ocurre
cuando se parte de cualquier estado y se sigue cualquier secuencia de entradas.
Si δ es la función de transición, entonces la función de transición extendida
construida a partir de δ será δ. La función de transición extendida es una
función que toma un estado q y una cadena w y devuelve un estado p (el estado
al que el autómata llega partiendo del estado q y procesando la secuencia de
entradas w). Definimos δ por inducción sobre la longitud de la cadena de
entrada como sigue: BASE. δ (q,ε) = q. Es decir, si nos encontramos en el
estado q y no leemos ninguna entrada, entonces permaneceremos en el estado q.
PASO INDUCTIVO. Supongamos que w es una cadena de la forma xa; es decir, a es
el último símbolo de w y x es la cadena formada por todos los símbolos excepto
el último. 3 Por ejemplo, w = 1101 se divide en x = 110 y a = 1. Luego δ(q,w) δ
(q,x),a (2.1) La Ecuación (2.1) puede parecer complicada, pero la idea es
simple. Para calcular δ(q,w), en primer lugar se calcula δ(q,x), el estado en
el que el autómata se encuentra después de procesar todos los símbolos excepto
el último de la cadena w. Supongamos que este estado es p; es decir, δ(q,x) =
p. Entonces δ(q,w) es lo que obtenemos al hacer la transición desde el estado p
con la entrada a, el último símbolo de w. Es decir, δ(q,w) = δ(p,a).
EJEMPLO 2.4 Deseamos diseñar un AFD que acepte el lenguaje L
= {w | w tiene un número par de ceros y un número par de unos} La tarea de los
estados de este AFD es la de contar el número de ceros y el número de unos
contando en módulo 2. Es decir, el estado se emplea para recordar si el número
de ceros es par o impar hasta el momento y también para recordar si el número
de unos leídos hasta el momento es par o impar. Existen por tanto cuatro
estados que pueden interpretarse de la manera siguiente: q0: tanto el número de
ceros como el de unos leídos hasta el momento es par. q1: el número de ceros
leídos hasta el momento es par, pero el de unos es impar. q2: el número de unos
leídos hasta el momento es par, pero el de ceros es impar. q3: tanto el número
de ceros como el de unos leídos hasta el momento es impar. El estado q0 es
tanto el estado incial como el único estado de aceptación. Es el estado inicial
porque antes de leer ninguna entrada, la cantidad de ceros y unos leídos hasta
el momento es igual a cero y cero es par. Es el único estado de aceptación
porque describe de forma exacta la condición para que una secuencia de ceros y
unos pertenezca al lenguaje L. Ahora ya sabemos cómo especificar el AFD para el
lenguaje L. Así A = ({q0,q1,q2,q3},{0,1},δ,q0,{q0}) donde la función de
transición δ se describe mediante el diagrama de transiciones de la Figura 2.6.
Observe cómo cada entrada 0 hace que el estado cruce la línea de puntos
horizontal. Así, después de leer un número par de ceros siempre estaremos por
encima de la línea en el estado q0 o q1, mientras que después de leer un número
impar de ceros siempre estaremos por debajo de la línea, en los estados q2 o
q3. Por el contrario, cualquier entrada 1 hace que el estado cruce la línea de
puntos vertical. Así, después de leer un número par de unos, siempre estaremos
en la parte izquierda, en el estado q0 o el estado q2, mientras que después de
leer un número impar de unos estaremos en la parte de la derecha, en los
estados q1 o q3. Estas observaciones constituyen una demostración informal de
que los cuatro estados tienen las interpretaciones que les hemos atribuido. Sin
embargo, debemos demostrar formalmente la corrección de las afirmaciones acerca
de los estados aplicando la inducción mutua.
También podemos representar este AFD mediante una tabla de
transiciones. La Figura 2.7 muestra esta tabla. Sin embargo, no sólo vamos a
ocuparnos del diseño de este AFD, sino que también queremos utilizarlo para
ilustrar la construcción de δ a partir de su función de transición δ.
Supongamos que la entrada es 110101. Dado que esta cadena tiene un número par
de ceros y unos, podemos asegurar que pertenece al lenguaje. Así, tendremos que
δ (q0,110101) = q0, ya que q0 es el único estado de aceptación. Verifiquemos
ahora esta afirmación. La comprobación supone calcular δ(q0,w) para cada
prefijo w de 110101, comenzando por ε y aumentando progresivamente el tamaño.
El resumen de este cálculo es: δ(q0,ε) = q0. δ(q0,1) = δ
δ(q0,ε),1 = δ(q0,1) = q1. δ(q0,11) = δ
δ(q0,1),1 = δ(q1,1) = q0. δ(q0,110) = δ
δ(q0,11),0 = δ(q0,0) = q2. δ(q0,1101) = δ
δ(q0,110),1 = δ(q2,1) = q3. δ(q0,11010) = δ
δ(q0,1101),0 = δ(q3,0) = q1. δ(q0,110101) = δ
δ(q0,11010),1 = δ(q1,1) = q0.
2.2.5 El lenguaje de
un AFD Ahora podemos definir el lenguaje de un AFD A = (Q,Σ,δ,q0,F). Este
lenguaje se designa por L(A) y se define como: L(A) = {w | δ(q0,w) pertenece a
F} Es decir, el lenguaje de A es el conjunto de cadenas w que parten del estado
inicial q0 y van hasta uno de los estados de aceptación. Si L es L(A) para un
determinado AFD A, entonces decimos que L es un lenguaje regular. EJEMPLO 2.5
Como hemos dicho anteriormente, si A es el AFD del Ejemplo 2.1, entonces L(A)
es el conjunto de todas las cadenas de ceros y unos que contiene una subcadena
01. En cambio, si A es el AFD del Ejemplo 2.4, entonces L(A) es el conjunto de
todas las cadenas de ceros y unos, cuya cantidad de ceros y unos es par. Introducción a la teoría de autómatas, lenguajes
y computación Notación estándar y variables locales Después de leer esta
sección, es posible que sea capaz de imaginar que la notación personalizada que
hemos empleado es necesaria; es decir, debe utilizar δ para designar la función
de transición, A para el nombre del AFD, etc. A lo largo de todos los ejemplos,
normalmente emplearemos las mismas variables para designar las mismas cosas, ya
que esto ayuda a recordar los tipos de variables, de la misma forma que una
variable i en un programa casi siempre designa un tipo entero. Sin embargo,
tenemos la libertad de denominar a los componentes de un autómata de la manera
que deseemos. Así, el lector es libre de denominar al autómata M y a su función
de transición T, si así lo desea. Además, no deberá sorprenderle que la misma
variable signifique cosas diferentes en contextos distintos.
Criterios Utilizados
para los caminos de Aceptación y no Aceptación:
En este programa describimos los criterios utilizados hacia
los caminos para que el programa nos acepte el autómata finito determinístico
para que sea aceptado así también para que nos muestre el error cuando no es un
autómata finito determinístico.
1.-Para que un autómata finito determinístico sea aceptado
que cumpla sus reglas.
2.-El programa no aceptara si el autómata no cumple dichas
reglas.
Conclusiones:
Teoría
de Autómatas: Rama de las ciencias de la
computación que estudia las máquinas abstractas y los problemas que éstas son
capaces de resolver.
Autómata
Finito (AF): Modelo computacional que realiza procesos
en forma automática sobre una entrada para producir una salida. Está conformado
por un alfabeto, un conjunto de estados finito, una función de transición, un
estado inicial y un conjunto de estados finales. M = (I, S, δ, F). Hay dos
tipos de AF: Los Autómatas Finitos Deterministas (AFD) y los Autómatas Finitos
No Deterministas (AFND).
Ejemplo
de AF: Interruptor de
apagado/encendido(on/off).
Autómata
Finito Determinista (AFD): M
= (Q, Σ, Δ, q0, F). El autómata no puede estar en más de un estado
simultáneamente.
Autómata
Finito No Determinista (AFND): M=(Q,
Σ, f, q0, F). Puede estar en varios estados al mismo tiempo.
-LISTADO DEL CODIGO
FUENTE DE LA CLASE DE LA MAQUINA Y LA APLICACIÓN DE PRUEBA
import
java.util.Scanner;
public class
Automata {
int cont;
char [] car;
boolean aceptado;
public static void main(String[] args) {
String cadena;
//String cadena ="ababa";
Scanner teclado=new Scanner(System.in);
Automata aut = new Automata();//
TODO code application logic here
cadena=teclado.next();
aut.car =
cadena.toCharArray();
aut.inicio();
if(aut.aceptado)
System.out.println("aceptacion");
else System.out.println("no
aceptacion");
}
public void
inicio(){
cont =0;
q0();
}
public void q0(){
System.out.println("En q0");
aceptado=false;
if(cont<car.length){
if(car[cont]=='a'){
cont++;
q1();
}else if(car[cont]=='b'){
cont++;
q4();
}
}//else System.out.println("En
error");
}
public void q1(){
System.out.println("En q1");
if(cont<car.length){
if(car[cont]=='b'){
cont++;
q2();
}}
//else System.out.println("En
error");
}
public void q2(){
System.out.println("En q2");
if(cont<car.length){
if(car[cont]=='a'){
cont++;
q2();
}else if(car[cont]=='b'){
cont++;
q3();
}
}//else System.out.println("En
error");
}
public void q3(){
System.out.println("En q3
");
aceptado=true;
if(cont<car.length){
if(car[cont]=='a'){
cont++;
q3();
}else if(car[cont]=='b'){
cont++;
qerror();
}
}//else System.out.println("En
aceptacion");
}
public void q4(){
System.out.println("En q4");
if(cont<car.length){
if(car[cont]=='a'){
cont++;
q4();
}else if(car[cont]=='b'){
cont++;
q5();
}
}//else System.out.println("En
error");
}
public void q5(){
System.out.println("En q5
");
aceptado=true;
if(cont<car.length){
if(car[cont]=='a'){
cont++;
q5();
}else if(car[cont]=='b'){
cont++;
qerror();
}
}//else System.out.println("En
aceptacion");
}
public void qerror(){
System.out.println("En error");
aceptado = false;
return;
}
}
BIBLIOGRAFIA:
Teoría de Autómatas y
Lenguajes Formales
SERAFIN MORAL
Universidad de granada
Introducción a la teoría de autómatas, Lenguajes y Computación.
HOPCROFT, J. E,, y ULLMAN, D
Addyson Wesley 20003.
https://www-db.sanford.edu/-ullman/ialc.hml.MaterialdellibrodeUllman(ingles)
