Expresiones Regulares

Expresiones
 regulares
 

Definición
 
Dado
 un
 alfabeto
 V
 ,
 los
 símbolos
 
 ,
 λ
 y
 los
 operadores
 +
 (unión),
 ・
 
(concatenación)
 y
 ∗ (clausura),
 definimos
 (de
 forma
 recursiva)
 una
 
expresión
 regular
 (ER)
 sobre
 el
 alfabeto
 V
 
 
como:
 

 
Ê 
Ê 
Ê 
Ê 
Ê 
Ê 

el
 símbolo
 Φ
 es
 una expresión
 regular
 
el
 símbolo
 ε
 
 es
 una
 ER
 
cualquier
 símbolo
 a
 ∈
 V
 es
 una
 ER
 
si
 α
 y
 β
 son
 ER
 entonces
 también
 lo
 es
 α +
 β
 
si
 α
 y
 β
 son
 ER
 entonces
 también
 lo
 es
 α
 ・
 β
 
si
 α
 es
 una
 ER
 entonces
 también
 lo
 es
 α∗
 

Expresiones
 regulares 
Ê El
 orden
 de
 prioridad
 de
 los
 operadores
 

es,
 de
 mayor
 a
 menor:
 ∗,
 ・,
 |.
 Este
 orden
 
puede
 alterarse
 mediante
 paréntesis,
 de
 forma
 análoga
 a
 como
 se
 hace
 con
 las
 
expresiones
 aritméticas.
 

Lenguaje
 descrito
 por
 una
 ER
 
Ê  Cada
 expresión
 regular
 α
 sobre
 un alfabeto
 V
 describe
 o
 

representa
 un
 lenguaje
 L(α)
 ⊆
 V
 ∗.
 

Ê  Este
 lenguaje
 se
 define
 de
 forma
 recursiva
 como:
 
Ê  si
 α
 =
 ε
 entonces L(α)
 =
 ε
 
Ê  si
 α
 =
 λ
 entonces
 L(α)
 =
 {λ}
 
Ê  si
 α
 =
 a
 y
 a
 ∈
 V
 entonces
 L(α)
 =
 {a}
 
Ê  si
 α
 y
 β
 son
 ER entonces
 L(α
 |
 β)
 =
 L(α)
 ∪
 L(β)
 
Ê  si
 α
 y
 β
 son
 ER
 entonces
 L(α
 ・
 β)
 =
 L(α)
 ・
 L(β)
 
Ê  si
 α∗
 es
 una
 ER
 entonces
 L(α∗) =
 (L(α))∗
 

Expresiones
 regulares
 
Ê  Ejemplo:
 Dado
 V
 =
 {0,
 1}
 y
 la
 ER
 
 α
 =
 0∗10∗,
 tenemos
 que:
 
 
Ê  L(0∗10∗)
 =
 L(0∗)...