CONVERSIÓN EXPRESIÓN REGULAR A UN AUTÓMATA FINITO NO DETERMINISTA

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 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:

bcastroJ@est.ups.edu.ec

castrO-bra12.jara@gmail.com

Castro_jara@hotmail.com

etc.

Expresión regular:

([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]=da1

[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

Para el siguiente paso habrá dos salidas

[A-Z]=da4

[a-z]=db4

Simulación JFLAP:

Diseño del AFND 

Pasos de la simulación

Ingreso de la cadena:

Link video:
video

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.