Informatica

Tema: Expresiones Regulares, Expresiones regulares en Autómatas Finitos
Integrantes:
ALEXIS BAUTISTA ERNESTO ACUÑA


EXPRESIONES REGULARES
Una expresión regular es una notación normalizada para representar lenguajes regulares. Como veremos, las expresiones regulares permiten describir con exactitud y sencillez cualquier lenguaje regular.
Para definir una expresión regular (e.r.) sepueden utilizar todos los símbolos del alfabeto Σ y, además, λ y Ø. Los operadores que también se pueden utilizar son:
+ representa la unión
. representa la concatenación (este símbolo no se suele escribir)
representa la clausura de Kleene
( ) modifican las prioridades de los demás operadores
1. La unión de dos lenguajes L y M, designada como L ∪ M, es el conjunto de cadenas que pertenecen a L,a M o a ambos. Por ejemplo, si L = {001,10,111} y M = {,001}, entonces L ∪ M = {,10,001,111}.
2. La concatenación de los lenguajes L y M es el conjunto de cadenas que se puede formar tomando cualquier cadena de L y concatenándola con cualquier cadena de M.

3.-La clausura (o asterisco, o clausura de Kleene)1 de un lenguaje L se designa mediante L∗ y representa el conjunto de cadenas que sepueden formar tomando cualquier número de cadenas de L, posiblemente con repeticiones (es decir, la misma cadena se puede seleccionar más de una vez) y concatenando todas ellas.

Algebra de las expresiones regulares ´
Sean α, β, γ expresiones Regulares
Propiedades de la unión (+)
1. Asociativa (α+β) +γ = α + (β +γ)
2. Conmutativa α +β = β +α
3. Elemento neutro () α += α
4. Idempotenciaα +α = α



Propiedades de la concatenación (.)
1. Asociativa (αβ)γ = α(βγ)
2. Distributiva respecto de la uni´on α(β +γ) = αβ +αγ
3. Elemento neutro () α = α = α
4. αØ=Ø
5. No es conmutativa


Propiedades del cierre de Kleene (*)
1. ∗ = 
2. Ø∗ = 
3. α∗α∗ = α∗
4. α∗α = αα∗
5. (α∗)∗ = α∗
6. α∗ = +αα∗
7. α∗ = +α +α2 +...+αn +αn+1α∗

Construcción de expresiones regularesEn una definición formal podemos decir que Para un alfabeto dado, los lenguajes regulares constituyen el enor conjunto de lenguajes sobre  que como decíamos al principio es cerrado respecto a las operaciones de concatenación, la clausrua de Klenne y la unión de lenguajes y además contiene el lenguaje vacio y los lenguajes unitarios {a} para a E 
Podemos describir las expresiones regularesrecursivamente del siguiente modo: cada expresión regular E, describimos el lenguaje que representa, al que denominaremos L(E).

CASO BASE
1. Las constantes ε y /0 son expresiones regulares, que representan a los lenguajes {ε } y /0, respectivamente.
Es decir, L(ε) = {ε } y L( /0) = / 0.
2. Si a es cualquier símbolo, entonces a es una expresión regular. Esta expresión representa el lenguaje{a}.
Es decir, L(a)= {a}.Observe que utilizamos la fuente en negrita para indicar la expresión correspondiente a un símbolo. La correspondencia, por ejemplo, que a hace referencia a a, es obvia.

PASO INDUCTIVO. Existen cuatro partes en el paso de inducción, una para cada uno de los tres operadores y otra para la introducción de paréntesis.
1. Si E y F son expresiones regulares, entonces E +Fes una expresión regular que representa la unión de L(E) y L(F). Es decir, L(E +F) = L(E) ∪ L(F).
2. Si E y F son expresiones regulares, entonces EF es una expresión regular que representa la concatenación de L(E) y L(F). Es decir, L(EF) = L(E)L(F).
3. Si E es una expresión regular, entonces E∗ es una expresión regular, que representa la clausura de L(E).
Es decir, L(E*) =(L(E)) *
4. Si E esuna expresión regular, entonces (E), una E encerrada entre paréntesis, es también una expresión regular, que representa el mismo lenguaje que E. Formalmente; L((E))= L(E).











Ejemplos:

Dado Σ = {a, b}, las siguientes afirmaciones son verdaderas:
∅ y {ε} son lenguajes regulares.
{a} y {b} son lenguajes regulares.
{a, b} es un lenguaje regular.
{ab} es regular.
{a^i|i ≥...