Expresiones Regulares

Capítulo 7: Expresiones Regulares
7.1. Concepto de expresión regular
7.1.1. Definición
7.1.2. Lenguaje descrito
7.1.3. Propiedades

7.2. Teoremas de equivalencia
7.2.1. Obtener un AFND apartir de una expresión regular
7.2.2. Obtener una expresión equivalente a partir de un
autómata finito

1

7.1. Concepto de Expresión Regular
El objetivo de las expresiones regulares esrepresentar todos los
posibles lenguajes definidos sobre un alfabeto Σ, en base a una
serie de lenguajes primitivos, y unos operadores de composición.
Lenguajes primitivos: el lenguaje vacío, el lenguajeformado
por la palabra vacía, y los lenguajes correspondientes a los
distintos símbolos del alfabeto.
Operadores de composición: la unión, la concatenación y el
cierre.
Ejemplo:
1. Lenguaje formadopor las cadenas que terminan en 01:
{0,1}*.{01}=
({0}∪{1})*.{01}
⇒ Expresión regular: (0+1)*01
2. Lenguaje formado por palabras de longitud par sobre a’s y
b’s:
{aa,ab,ba,bb}*=({aa}∪{ab}∪{ba}∪{bb})*
⇒Expresión: (aa+ab+ba+bb)*

2

7.1.1 Definición
Dado un alfabeto Σ, las expresiones regulares sobre Σ se definen
de forma recursiva por las siguientes reglas:
1. Las siguientes expresionesson 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:
1. ()
2. * cierre
3. . concatenación
4. +unión
Ejemplo:
Algunos ejemplos de expresión regular son:
(0 + 1)*01
(aa + ab + ba + bb)*
a*(a + b)
(aa)*(bb)*b

3

7.1.2 Lenguaje descrito por una ER
Definición (Lenguaje descrito por unaER):
Sea r una expresión regular sobre Σ. El lenguaje descrito por r,
L(r), se define recursivamente de la siguiente forma:
1. Si r=∅
⇒ L(∅)= ∅
2. Si r=λ
⇒ L(λ)= {λ}
3. Si R=a, a∈Σ ⇒...