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 a partirde 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 es representartodos 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 lenguaje formadopor 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 formado por lascadenas 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 expresiones son expresionesregulares 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 ejemplosde 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 una ER): 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∈Σ ⇒ L(a)= {a} 4. Si R=α+β ⇒ L(α+β)= L(α)∪L(β) 5. Si R=α.β...