Expresiones regulares

EXPRESIONES REGULARES
Las expresiones regulares son expresiones simples que describen con facilidad los lenguajes aceptados por un autómata finito. Además en este trabajo introduciremos las operaciones de concatenación y cerradura sobre un conjunto de cadenas, además de definir las expresiones regulares también probaremos que los lenguajes aceptados por los autómatas finitos son los lenguajesque se pueden escribir con expresiones regulares, Ej.
Sea L_1 y L_2 conjuntos de cadenas ∑^*, La concatenación de L_1 y L_2 denotada como L_1 L_2. Es decir L^* denota palabras construidas mediante la concatenación de cualquier número de palabras de L. L^+ es lo mismo que L^*, sólo que ahora se excluye el caso de cero palabras, cuya “concatenación” se define como ϵ. Nótese que L^+ contiene a ϵ siy sólo si L lo hace.
Ejemplo. Sea L_1 = {10,1} y L_2 = {011,11}. Entonces L_1 L_2 = {10011, 1011,111}.
También {10,11}* = { ϵ, 10, 11, 1010, 1011, 1110, 1111,…}.
Si ∑ es un alfabeto, entonces ∑^* denota todas las cadenas de símbolos de ∑, como se estableció previamente. Nótese que no hacemos distinción entre ∑ como un alfabeto y ∑ como un lenguaje de cadenas de longitud 1.
Sea ∑ unalfabeto. La expresión regular sobre ∑ y los conjuntos que denotan se definen de manera recursiva como sigue.
∅ es una expresión regular y denota al conjunto vacío.
ϵ es una expresión regular y denota al conjunto { ϵ }.
Para cada a en ∑ , a † es una expresión regular y denota al conjunto {a}.
Si r y s son expresiones regulares que denotan a los lenguajes R y S, respectivamente, entonces (r + s),(rs) y (r*) son expresiones regulares que denotan a los conjuntos R ∪ S, RS y R*, respectivamente.
Al escribir expresiones regulares podemos omitir muchos paréntesis si suponemos que * tiene prioridad sobre la concatenación sobre +. Por ejemplo, ((0(1*))+0) puede escribirse como 01*+0. También podemos abreviar la expresión rr* escribiendo r^+. Cuando sea necesario distinguir entre una expresiónregular r y el lenguaje denotado por r, utilizaremos L(r), para este último. Cuando no haya lugar a confusiones utilizaremos r para las expresiones regulares y para el lenguaje denotado por la expresión regular.
Ejemplo 2. 00 es la expresión regular que representa a {00}. La expresión {0 + 1}* denota a todas las cadenas de ceros y unos. Por tanto {0 + 1}*00 {0 + 1}* representa a todas lascadenas de ceros y unos con al menos dos ceros consecutivos. La expresión regular {0 + 1}* denota a todas las cadenas de 0s y 1s que comienzan con 1 y no tienen dos ceros consecutivos. †† Aún más, dad alguna cadena que comience con 1 y que no tenga ceros consecutivos, uno puede partir dicha cadena en unos, seguidos de un 0, si existe. Por ejemplo, 1101011 puede partirse en 1-10-10-1-1. Esta particiónmuestra que cualquiera de estas cadenas está en 〖{0 + 1}〗^(i.)

Fig. A1 a) Para la Unión. B) para la concatenación c) Para la cerradura.

La construcción de M está dada en la fig. A1(b). cada trayectoria en M de q_1 a q_2 es una trayectoria etiquetada con alguna cadena x y va de q_1 a f_1, seguida por el borde de f_1 a q_2 etiquetado con ϵ, seguido, a su vez, por una trayectoria etiquetadacon alguna cadena y que va de q_2 a f_2. Por tanto, L(M) = {xy | x está en L(M) y y está en L(M_2) } y L (M) = L(M_1) L(M_2) como se quería demostrar.
Ejemplo. Construyamos un NFA para la expresión regular 01 (*)+ 1. Tomando en cuenta las reglas que acabamos de discutir, esta expresión en realidad es (0(1*))+1, así que es de la forma r_1 + r_2, en donde r_1= 01* y r_2 = 1. El autómata para r_2es fácil, éste es

Podemos expresar r_1 como r_3 r_4, en donde r_3= 0 y r_4= 1*. El autómata para r_3 también es fácil:

A su vez, r_4 es r_5*, en donde r_5 es 1. Un autómata para r_5 es

Nótese la necesidad de mantener los estados autómatas diferentes disjuntos nos prohíbe utilizar el mismo NFA para r_2 y r_5, aunque sean la misma expresión. Para construir un NFA para r_4 = r_5*...