vida

Nombre: Luis Antonio Farías Tello
Escuela: Ing. en Sistemas y Computación
Nivel: 5
Materia: Autómatas

Concepto de Expresión Regular
El objetivo de las expresiones regulares es representartodos los posibles lenguajes definidos sobre un alfabeto S, 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)
Operaciones con expresiones regulares.
  Selección: Si r y s son expresiones regulares, la selección se denota r|s y se define por cualquier cadena que concuerda con r o s Entérminos de lenguaje L(r|s) = L(r) U L(s) La selección se puede extender a más de dos alternativas L(a|b|c|d) = {a,b,c,d}
  Concatenación: Consiste en la yuxtaposición de los caracteres sin un carácterintermedio. La concatenación de las expresiones regulares r y s se denota rs En términos de lenguaje L(rs) = L(r)L(s) La concatenación tambien se puede extender a más de dos expresiones regulares.
 Repetición: Denominada tambien cerradura de Kleene, se denota r* donde r es una expresión regular y corresponde a cualquier concatenación finita de las cadenas r así r* = { } U r U rr U rrr U ….Precedencia de operaciones1.  Repetición2.  Concatenación3.  Selección de alternativasCuando la precedencia es diferente, debemos usar paréntesis para denotarlo.




Construcción de expresionesregulares.
Definición inductiva de regexp´s:
Base:  es una expreg y  es una expreg. L()=, y L()= .
Si a  , entonces a es una expreg. L(a)= a
Inducción
Si E es una expreg, entonces...