Todo

2.2. EXPRESIONES REGULARES.
2.4. EXPRESIONES REGULARES.
Los lenguajes aceptados por un autómata finito se describen con facilidad mediante expresiones simples llamadas expresiones regulares.
Sea  un alfabeto. La expresión regular sobre  y los conjuntos que denotan se definen de manera recursiva como sigue:
1.  es una expresión regular y denota al conjunto vacío.
1.  es unaexpresión regular y denota al conjunto { }.
1. Para cada a   , a es una expresión regular y denota al conjunto {a}.
1. Si r y s son expresiones regulares que denotan a los lenguajes R y S.; respectivamente, entonces tenemos lo siguiente:
r+s es una expresión regular que denota a los conjuntos R  S.
(r) es una expresión regular que denota al conjunto R.
rs es una expresión regular quedenota a los conjuntos RS.
r* es una expresión regular que denota al conjunto R*.
r+ es una expresión regular que denota al conjunto R+.
ri es una expresión regular que denota al conjunto Ri.
Ejemplo de Autómatas con sus expresiones regulares
El lenguaje del autómata de la figura 2.13. esta formado por cualquier cadena de 1’s, incluyendo  .

 Para ver el gráfico seleccione la opción ¨Bajartrabajo¨ del menú superior
 Figura 2.13. La expresión regular del autómata es: 1*
El lenguaje del autómata de la figura 2.14. esta formado por todas las cadenas de a’s de longitud par, incluyendo  .
 Para ver el gráfico seleccione la opción ¨Bajar trabajo¨ del menú superior
 Figura 2.14. La expresión regular del autómata es: (aa)*
El lenguaje del autómata de la figura 2.15. esta formado porcadenas de cero ó más a’s seguidas de cero ó más b’s.
 Para ver el gráfico seleccione la opción ¨Bajar trabajo¨ del menú superior
 Figura 2.15. La expresión regular del autómata es: a*b*.
Existen muchas equivalencias con respecto a expresiones regulares basadas en las correspondientes igualdades de lenguajes. Por ejemplo sean r, s y t expresiones regulares sobre el mismo alfabeto  . Entonces:1. r + s = s + r
2. (rs)t = r(st)
3. (r + s)t = rt + st
4. (r*)* = r*
5. r(s + t) = rs + rt

2.5. LENGUAJES REGULARES.
Los lenguajes regulares pueden ser usados en la construcción de analizadores léxicos - programas que analizan un texto y extraen los lexemas ( o unidades léxicas) que hay en el mismo -.
El conjunto de los lenguajes regulares sobre un alfabeto  estaformado por el lenguaje vacío, los lenguajes unitarios incluido { } y todos los lenguajes obtenidos a partir de la concatenación, unión y cerradura de estrella de lenguajes.

Ejemplo de lenguajes regulares:
Expresión Regular | Lenguaje Regular |
10 | L={La cadena de 10} |
  |   |
1 + 0 | L={Una cadena de 0 ó una cadena de 1} |
  |   |
1* | L={Cualquier cadena de 1’s incluyendo  } |  |   |
(00)* | L={Cadenas de 0’s de longitud par, incluyendo  } |
  |   |
0*1* | L={Cadenas de ninguno o más 0’s concatenadas a cadenas de ninguno o más 1’s} |
  |   |
1(1 + 0)* | L={Todas las cadenas sobre el alfabeto {1, 0} que empiecen con 1} |
  |   |
(1 + 0)*00 | L={Todas las cadenas sobre el alfabeto {1, 0} que terminen en 00} |
  |   |
(1 + 0)*00(1 + 0)* | L={Cualquiercombinación de 0’s ó 1’s que contengan al menos dos ceros consecutivos} |
Cuando sea necesario distinguir entre una expresión regular r y el lenguaje denotado por la misma, usaremos L(r) para denotar el lenguaje. En cualquier caso, si se afirma que w  r, ello equivale a decir que w  (r). Si r y s son expresiones regulares sobre el mismo alfabeto y si L(r)= L(s), entonces se dice que r y s sonequivalentes. En el caso de que r y s sean equivalentes se puede escribir r= s. También se puede usar r s en el caso de que L(r)  L(s).

2.6. FUNCIONES RECURSIVAS.
Una definición recursiva esta caracterizada por un proceso de tres pasos:
1. Declaración de los objetos básicos que pertenecen al lenguaje (caso base).
2. Otorgar las reglas para construir más objetos a partir de los...