Expresiones regulares

              CENTRO UNIVERSITARIO UAEM 

              ATLACOMULCO

            LICENCIATURA EN INGENIERÍA EN COMPUTACIÓN

              NOMBRE DEL DOCENTE:

         INGENIERO. HÉCTOR CABALLERO HERNÁNDEZ

              NOMBRE MATERIA:

AUTÓMATAS Y LENGUAJES FORMALES

              NOMBRE DE LA ALUMNA:

HEIVILINA PÉREZ ARIAS

              GRUPO:

ICO-19

              TURNO:

MATÚTINO

               TRABAJO A ENTREGAR:

                                                      LENGUAJES REGULARES

              FECHA DE ENTREGA:

MAYO DE 2015.   

LENGUAJES REGULARES
*GRAMATICAS REGULARES - EXPRESIONES REGULARES
**LENGUAJES REGULARES
Sea S = { a1, …, an} entonces definimos el conjunto de los lenguajes regulares en forma recursiva como
sigue:
Casos Base:
· { } es un lenguaje regular
· {l} es un lenguaje regular
· " 1 £ i £ n {a1} es un lenguaje regular
Casos Inductivos
· Si L1 es un lenguaje regular Ù L2 es un lenguaje regular ⇒ (L1.L2) es un lenguaje regular
· Si L1 es un lenguaje regular Ù L2 es un lenguaje regular ⇒ (L1ÈL2) es un lenguaje regular
· Si L1 es un lenguaje regular ⇒ L* es un lenguaje regular
· Si L1 es un lenguaje regular ⇒ L+ es un lenguaje regular
Ejemplo:
S = { a,b,c}
L1 = {a, ab, b, ccc} es regular? SI.
Demostración:
1. Si considero los lenguajes:
L11 ={a} L12 ={ab} L13 ={b} L14 ={ccc}
puedo decir que L1 = L11 È L12 È L13 È L14
2. L11 es regular? Sí, por 3er caso base.
Lo mismo ocurre con L13
3. L12 es regular?
Puedo decir que L12 = L11 . L13
Por lo tanto, por primer caso inductivo, L12 es regular
4. L14 es regular?
Si considero el lenguaje L15 = {c}
Puedo decir que L14 = L15 . L15 . L15
Por lo tanto, por primer caso inductivo, L14 es regular
5. Entonces, si volvemos al principio:
L1= {a} È {ab} È {b} È {ccc}
Podemos decir, por 2do caso inductivo, que L1 es regular

**Expresiones regulares
Se denominan expresiones regulares sobre un alfabeto A, a las expresiones que se pueden construir a
partir de las siguientes reglas:
- Æ es una expresión regular que describe el lenguaje vacío;
- l es una expresión regular que describe el lenguaje {l}, esto es el lenguaje que contiene
únicamente la cadena vacía;
- Para cada símbolo a Î A, a es una expresión regular que describe el lenguaje {a}, esto es el
lenguaje que contiene únicamente la cadena a;
- Si r y s son expresiones regulares que describen los lenguajes L(r) y L(s) respectivamente:
i) r / s es una expresión regular que describe el lenguaje L(r) È L(s)
ii) r . s es una expresión regular que describe el lenguaje L(r) . L(s)
iii)r* es una expresión regular que describe el lenguaje L(r)*.
El operador de clausura es el que tiene mayor precedencia, seguido por el operador de concatenación y
por último el operador de unión.
Las expresiones regulares describen los lenguajes regulares (aquellos reconocidos por autómatas finitos).
Por ejemplo las siguientes son expresiones regulares válidas:
- a* . b que describe el lenguaje L = {anb / n ³ 0}
- (a / b)* que describe el lenguaje L = { x / x Î {a, b}* }