CONVERSIÓN
EXPRESIÓN REGULAR A UN AUTÓMATA FINITO NO DETERMINISTA
BRAULIO ROMAN
CASTRO JARA
UNIVERSIDAD
POLITÉCNICA SALESIANA
INGENIERIA EN
SISTEMAS
LENGUAJES FORMALES
2017-2018
Conversión
expresión regular a un autómata finito no determinista
Introducción:
El objetivo de las
expresiones regulares es representar todos los posibles lenguajes definidos
sobre un alfabeto Σ, en base a una serie de lenguajes primitivos, y unos
operadores de composición. Mientras que un AFND posee al menos un estado q ∈ Q, tal que para un
símbolo a ∈
Σ del alfabeto, existe más de una transición δ(q,a) posible. Al saber esto se
puede realizar una conversión de la ER a un AFND.
Los AFND no son tan deseados
dentro de los lenguajes regulares, debido a que dificultan su implementación tanto
mecánica como informática, la mayoría de transformaciones interno de
expresiones regulares a gramáticas regulares conducen a AFND, por lo que se
considera imprescindibles en análisis epigráfico. Por lo cual en este informe
se describe la conversión de expresión
regular a un autómata finito no
determinista
Objetivos:
· Diseñar
una expresión regular que cumpla con los conocimientos adquiridos en clase
· Convertir
esa ER en un AFND
Marco
teórico:
Expresiones
regulares:
Una expresión regular es
una secuencia de caracteres a partir de un alfabeto que forman un patrón de
búsqueda. Las expresiones regulares se construyen utilizando los operadores de
unión y concatenación. Toda expresión regular tiene algún autómata finito
asociado.
Dado un alfabeto Σ, las
expresiones regulares sobre Σ se definen de forma recursiva por las siguientes
reglas: (Artificial, 2018)
1.
Las siguientes expresiones son expresiones
regulares primitivas:
· ∅
· Λ
· a,
siendo a ∈ Σ.
2.
Sean α y β expresiones regulares, entonces
son expresiones regulares derivadas:
· α+β
(unión)
· α.β
(o simplemente αβ) (concatenación)
· α* (cierre)
· (α)
3. No
hay más expresiones regulares sobre Σ que las construidas mediante estas
reglas.
Precedencia de los
operadores: (Artificial, 2018)
· ()
· *
cierre
· Concatenación
· + unión
Autómatas
finitos no deterministas:
Es similar al AFD donde
solo existe una posible acción en cada momento, pero en un AFND se puede elegir
entre varias alternativas de transición.
En un momento dado, en un AFND pueden suceder lo
siguiente:
1. Existen
varias transiciones posibles aplicables.
2. Las
transiciones de las AFND pueden ser inciertas
3. Un
AFND acepta una cierta cadena si es posible, que tras analizarla el autómata
puede en uno de los estados de aceptación.
DEFINICION:
Fig 2. Autómata finito no determinista
Ejemplo de AFND
El conjunto de estados Q será el conjunto potencia del conjunto de estados del autómata no determinista. Así, Q={{p}, {q}, {p, q}, 0}.
El conjunto de estados Q será el conjunto potencia del conjunto de estados del autómata no determinista. Así, Q={{p}, {q}, {p, q}, 0}.
El estado inicial es el
estado correspondiente al subconjunto formado por el estado inicial del
autómata no determinista. Así, el estado inicial de A es {p}.
Los estados de aceptación
son los estados correspondientes a los subconjuntos que contengan uno o más
estados de aceptación. Así, en el presente ejemplo, los estados de aceptación
son {q} y {p, q}. (Vázquez, 2017)
Procedimiento:
Expresiones regular para validar direcciones de correo
electrónico de los siguientes tipos:
etc.
([A-Z|a-z|0-9] {3,}) ([\.|_|-]([A-Z|a-z|0-9]{3,})){0,2}(@)([A-Z|a-z]{2,})(\.([A-Z|a-z]{2,})){1,3}
Dados los alfabetos
[A-Z] Letras mayúsculas
de la (A) a la (Z)
[a-z] Letras minúsculas
de la (a) a la (z)
[0-9] Números del (0) al
(9)
[\. |_|-] Caracteres
especiales como (.), (_) y (-)
Construcción:
Al unir los alfabetos descritos anteriormente se puede
construir la expresión regular
Paso
1.
Validamos la entrada de
mayúsculas o minúsculas o números los cuales deben tener como mínimo 3
caracteres de los alfabetos antes mencionados.
Ejemplo
práctico:
([A-Z|a-z|0-9] {3,})
{3,} à aquí se da el
rango de mino 3 máximo indefinido
Paso
2.
Después de que se ingrese
una letra mayúscula o minúscula o número debe ingresarse los caracteres
especiales estos pueden ser (.) o (-) o (_) seguidos de una palabra, como
máximo se puede agregar tres grupos de caracteres conformados por letras
mayúsculas, minúsculas y números oh cada grupo individual seguido de un
carácter especial ejemplo: abc.abc-abc oh abc-abc_abc, etc.
Ejemplo
práctico:
([\. |_|-]([A-Z|a-z|0-9]{3,})){0,2}
{0,2}à rango de 0 a 2
Paso
3.
Después de la entrada de
los grupos de caracteres antes mencionados debe seguir una @
Ejemplo
práctico:
(@)
Paso
4.
Se validará el ingreso de cadenas de texto con letras
mayúsculas y minúsculas como mínimo dos letras.
Ejemplo
práctico:
([A-Z|a-z] {2,})
{2,} rango mínimo dos, máximo indefinido
Paso
5.
En este paso y el final
se validará el ingreso de 4 grupos máximo de palabras conformadas por letras mayúsculas
y minúsculas como mínimo de grupo dos palabras cada grupo será separado por un
(.)
Ejemplo
práctico:
(\. ([A-Z|a-z] {2,})) {1,3}
Fig 2. Expresiones
regular para validar direcciones de correo electrónico
Conversión
expresión regular a un autómata finito no determinista:
([A-Z|a-z|0-9] {3,}) ([\.|_|-]([A-Z|a-z|0-9]{3,})){0,2}(@)([A-Z|a-z]{2,})(\.([A-Z|a-z]{2,})){1,3}
Paso
1. [A-Z|a-z|0-9] = d1
0 será el estado inicial el cual tendrá tres salidas
para la transición al siguiente estado
[a-z]=db1
[0-9]=dc1
Paso
2. [\. |_|-] = c1
Para la siguiente transición se contará con el
siguiente conjunto de transiciones
\. =ca1
_=cb1
-=cc1
Pas
3.) [A-Z|a-z|0-9] = d2
Tendrá tres salidas las cuales son:
[A-Z]=da2
[a-z]=db2
[0-9]=dc2
Paso
4.) @ = @
La siguiente transición solo tendrá una salida la cual
es el signo @
Paso
5.) [A-Z|a-z] = d3
Para el siguiente paso
habrá dos salidas
[A-Z]=da3
[a-z]=db3
Paso
6.) \. = p
La siguiente transición solo tendrá una salida la cual
es el signo (.)
Paso 7.) [A-Z|a-z] = d4
[A-Z]=da4
[a-z]=db4
Simulación
JFLAP:
Diseño
del AFND
Pasos
de la simulación
Ingreso
de la cadena:
Conclusión:
Para alcanzar los
objetivos que se plantearon, se aplicó ejemplos como la ER en la cual se logró
validar el correo electrónico, mediante tres caracteres haciendo uso de letras
mayúsculas y minúsculas separadas por puntos, en cuanto a la AFND nos da varias
transiciones posibles, es decir varias maneras de llegar a un fin. En cuanto a
lo laboral estos algoritmos o lenguajes formales nos ayuda a resolver problemas
en el mundo real como en programación, o bien podría decir a interpretar
resultados.
Referencias
Artificial, G. d. (2018). ia.urjc. Recuperado el
31 de Julio de 2018, de
http://www.ia.urjc.es/grupo/docencia/automatas_itis/apuntes/capitulo7.pdf
Vázquez, E. G. (2017). Introduccion
a la Teoría de Autómatas Gramáticas y Lenguajes. Editorial Universitaria
Ramón Araces.
