Lenguajes Y Gramaticas Regulares

Lenguajes Regulares y
Gramáticas Regulares
Lenguajes Formales
Ing. Daniel Díaz

Alexis Cruz
UNIVERSIDAD POLITECNICA SALESIANA Ing. De Sistemas

Alexis Cruz

LENGUAJES FORMALES
Resumen ejecutivo:
A veces necesitamos encontrar algo concreto en un texto o cadena, o reemplazar algo por otra
cosa; ya sea en una aplicación, o en un lenguaje de programación. Por ejemplo, si queremos
buscar "tag" yreemplazarlo por "etiqueta" la mayoría de aplicaciones o lenguajes tienen una
función para hacerlo de forma sencilla.
Pero a veces lo que queremos hacer es más complejo, porque puede que en vez de ser una
palabra o parte de palabra simple, necesitemos hacer algo como "búscame todas las palabras
que acaben en 'f' y que empiecen por un número del 2 al 71" (por ejemplo) o "reemplaza las
palabras quecontengan este grupo de letras por esto".
En estos casos podemos utilizar las expresiones regulares (que se pueden llamar regex o regexp
de forma abreviada), que es como un lenguaje para poder definir exactamente qué es lo que
queremos buscar o reemplazar.

Marco teórico:

Figura 1-RELACIÓN LENGUAJES, EXPRESIONES, GRAMÁTICAS REGULARES Y AUTÓMATAS FINITOS

Como se muestra en la figura:
 Los lenguajesregulares son la clase de lenguajes aceptados por los Autómatas Finitos.
 Los lenguajes regulares pueden ser representados mediante: Expresiones Regulares y
Gramáticas Regulares
 Los lenguajes regulares son los más simples y restringidos según la jerarquía de
Chomsky.

Alexis Cruz

LENGUAJES FORMALES

Lenguajes Regulares
Los lenguajes regulares se llaman así porque sus palabras contienen“regularidades” o
repeticiones de los mismos componentes, como por ejemplo en el lenguaje L1 siguiente:
L1 = {ab, abab, ababab, abababab, . . .}
En este ejemplo se aprecia que las palabras de L1 son simplemente repeticiones de “ab”
cualquier número de veces. Aquí la “regularidad” consiste en que las palabras contienen “ab”
algún número de veces.
Otro ejemplo más complicado sería el lenguaje L2 :
L2 ={abc, cc, abab, abccc, ababc, . . .}
La regularidad en L2 consiste en que sus palabras comienzan con repeticiones de “ab”, seguidas
de repeticiones de “c”. Similarmente es posible definir muchos otros lenguajes basados en la
idea de repetir esquemas simples. Esta es la idea básica para formar los lenguajes Regulares.
Adicionalmente a las repeticiones de esquemas simples, vamos a considerar que loslenguajes
finitos son también regulares por definición. Por ejemplo, el lenguaje L3 = {anita, lava, la, tina}
es regular.
Finalmente, al combinar lenguajes regulares uniéndolos o concatenándolos, también se
obtiene un lenguaje regular. Por ejemplo, L1 ∪ L3 = {anita, lava, la, tina, ab, abab, ababab,
abababab, . . .} es regular. También es regular una concatenación como L3 L3 = {anitaanita,
anitalava,anitala, anitatina, lavaanita, lavalava, lavala, lavatina, . . .}
Definición.- Un lenguaje L es regular si y sólo si se cumple al menos una de las condiciones
siguientes:
•

L es finito;

•

L es la unión o la concatenación de otros lenguajes regulares R1 y R2, L = R1 ∪ R2 o L = R1
R2 respectivamente.

•

L es la cerradura de Kleene de algún lenguaje regular, L = R∗.

Esta definición nos permiteconstruir expresiones en la notación de conjuntos que representan
lenguajes regulares.
Ejemplo.- Sea el lenguaje L de palabras formadas por a y b, pero que empiezan con a, como
aab, ab, a, abaa, etc. Probar que este lenguaje es regular, y dar una expresión de conjuntos
que lo represente.
Solución.- El alfabeto es Σ = {a, b}. El lenguaje L puede ser visto como la concatenación de una a
con cadenascualesquiera de a y b; ahora bien, éstas últimas son los elementos de {a, b}∗,
mientras que el lenguaje que sólo contiene la palabra a es {a}. Ambos lenguajes son regulares.
Entonces su concatenación es {a}{a, b}∗ , que también es regular.

Alexis Cruz

LENGUAJES FORMALES

Gramáticas regulares
La representación de los lenguajes regulares que aquí estudiaremos se fundamenta en la
noción de...