Jesús Rodríguez

Expresiones  Regulares v  Definición:  Las expresiones regulares             representan lenguajes regulares y su            propósito es simplificar la escritura de            los lenguajes regulares. Recursivamente           una expresión regular  sobre un alfabeto            å dado se define como: ü  Expresiones Regulares básicas:             -  Ø  es una expresión  regular que                representa al lenguaje  Ø.            -   l   es una expresión  regular que                representa al  lenguaje {l           -   a es una expresión  regular que               representa al lenguaje {a}, aÎå. ü  Si   R y S son expresiones regulares sobre å  también lo son:             -   R.S (Concatenación.)             -   R U S (Unión.)

-   R* (Clausura de Kleene Representado                          por el  lenguaje R). v  Ejemplo: Dado el alfabeto å ={a, b, c}, se  tiene  que: -          (a Ub*)a*(bc)* es una expresión  regular que representa  al   lenguaje              ({a}U{b}*).{a}*·{bc}*). v  Nota: Es importante destacar que toda expresión regular sobre  å, denota  un lenguaje regular sobre å. v  Ejemplo: A continuación  se presentan dos ejemplos de expresiones regulares. -          ab1      Representa el  lenguaje formado por palabras o cadenas  que empiezan en  a  seguida de ninguna una o mas b’es. -          (aUb)*  : Representa una palabra formada por a, b o más caracteres que puedan ser a o b.

Lenguaje  Generado por una Expresión Regular Definición: Se puede definir recursivamente un lenguaje  regular L, por medio de una expresión regular haciendo  uso de las siguientes reglas de calculo.     -   Si   a=Æ     entonces    L(a)=Æ.     -   Si   a=l      entonces    L(a)=ílý.     -   Si   a= a,  aÎå,  entonces L(a)=íaý.     -   Si   a y b  son  ER, entonces L (a+b)=L(a) U L(b).     -   Si   a y b  son  ER, entonces L (a.b)=L(a) . L(b).     -   Si    a  es  ER, entonces  L(a1) =L(a)1     -   Si    a  es  ER, entonces  L ((a))=L (a). Ejemplo: Para  la expresión  regular  ab1        se tiene  que el lenguaje regular asociado es:   L(ab1) =L(a)L(-ab1) =íýL(b)1=íý

EXPRESIONES REGULARES

Son los lenguajes formales más simples, con los mecanismos de representación y reconocimiento más estudiados. Su aplicación práctica en la teoría y construcción de intérpretes y compiladores de lenguajes de programación o de especificación o formato de información, especialmente como microcomponentes del analizador lexicográfico que detecta los tókenes como constantes numéricas, cadenas de texto, operadores, palabras reservadas (keywords), separadores, etc. Pero también se puede apreciar su uso en máquinas expendedoras, teléfonos públicos, calculadoras y otros artefactos electromecánicos.

Definiciones:

Se dice que un lenguaje es regular si y sólo si se cumple cualquiera de las siguientes proposiciones:

  Tiene al menos una gramática regular G que lo produce.

  Puede ser reconocido por un autómata finito A.

  Existe una expresión regular Er que representa a todas las cadenas de L.

Dentro de la Jerarquía de Chomsky se refiere a los lenguajes de tipo 3, el subconjunto de lenguajes formales mas restringido dentro de la jerarquía, como se ve en la imagen.

También puede realizarse una definición recursiva-constructiva de los lenguajes regulares mediante el álgebra de lenguajes formales.

Un lenguaje regular sobre un alfabeto T ó LR(T) es:

1. El lenguaje vacío {}.

2. El lenguaje conformado por la cadena vacía   o lenguaje trivial.

3. Un lenguaje {x} conformado por un único símbolo x de T.

4. Si A y B son lenguajes regulares sobre T, entonces AB (Concatenación de lenguajes), Archivo:A union B.gif (Unión de lenguajes), A*(Clausura de lenguaje o Estrella de Kleene) son también lenguajes regulares sobre T.

5. Cualquier otro lenguaje que pueda obtenerse a partir de 1 a 4.

Ejemplo:

Demuestre que el lenguaje conformado por los nombres de variables de PROLOG es un lenguaje regular.

Primero debe recordarse que un nombre de variable PROLOG viene dada por la forma:

Cualquier palabra que comience con una letra mayúscula seguida o no de combinaciones de letras, cifras o subrayados o que comience con al menos un subrayado seguido o no de cualquier secuencia de alfanuméricos o subrayados.

Cada de las siguientes construcciones son equivalentes en virtud de la definición dada antes:

  La expresión regular (A|B|...|Z)|_(A|B|...|Z|a|b|...|z|_)*.

  El siguiente autómata finito representado como diagrama de estados permite el reconocimiento de variables de PROLOG.

Importancia de los lenguajes regulares:

La existencia y formalización de los lenguajes regulares (LR) y su vinculación con otros artefactos lingüísticos-matemáticos ya bien formalizados, estudiados e incluso llevados a la práctica ha sido de vital importancia en el ulterior desarrollo de los mecanismos de procesamiento de lenguajes de computadora, fundamentalmente en los analizadores lexicográficos gracias a la posibilidad de derivar el reconocimiento de los LR mediante autómatas finitos que son fáciles de implementar computacionalmente con mecanismos simples y rápidos, óptimos en la obtención de parsers veloces y robustos que a su vez le ofrecen a los desarrolladores información detallada de los errores léxicos, sintácticos e incluso advierten sobre errores semánticos.

Lo mismo sucede por ejemplo con las expresiones regulares implementadas ya en muchos Lenguaje de programación de propósito general modernos que permiten a los desarrolladores de lenguajes mecanismos muy eficientes para la obtención intuitiva de partes de compiladores que reconocen los tókenes o partículas lexicales del código fuente como fase del proceso completo de interpretación o compilado, según sea el caso.

A manera de ilustración en el caso del ejemplo anterior vemos la siguiente función Python que a partir de cualquiera de los elementos formalizadores del LR correspondiente permite decidir si un texto w es una variable PROLOG: