Lenguajes Regulares

LENGUAJES REGULARES

Lenguajes sobre alfabetos

Para un alfabeto S = {a1,a2,…,an} se pueden numerar las palabras de S* de la siguiente manera:

e 0

a1 1

a2 2

. .

an n

a1a1 n+1

a1a2 n+2

para S = {a, b}, podemos numerar sus cadenas con dígitos binarios 1 y 2 en vez de 0 y 1. Sea a el 1 y b el 2, entonces se obtiene

e 0

a 1

b 2

aa 11 = 3

ab 12 = 4

abaa 1211 = 19

de esta manera se representa cada cadena como un entero único.

Y cualquier número podemos representarlo como una secuencia de a’s y b’s, por ejemplo el 32 se convierte a 11112 y luego a aaaab.

Teorema 1. Para todo alfabeto S, S* es infinito enumerable.

Teorema 2. El conjunto de todos los lenguajes sobre S no es numerable.

Demostración. Llamemos L al conjunto de todos los lenguajes sobre S, si L es numerable, por tanto podemos enumerarlo como A0, A1, A2, …

S* puede numerarse como w0, w1, w2, … Sea B = {wi | wi Ï Ai}. B contiene las palabras que no pertenecen al lenguaje que tienen el mismo índice que las mismas. Pero como B es un lenguaje B = Ak para algún k. Si wk Î B, entonces wk Ï Ak = B. Y por lo tanto wk esta y no esta en Ak. Lo mismo sucede si suponemos wk Ï B. Por lo tanto L no es numerable.

El teorema 2 estipula que hay una cantidad innumerable de lenguajes sobre un alfabeto particular.

Por tanto, no existe ningún método de especificación de lenguajes que sea capaz de definir todos los lenguajes sobre un alfabeto

Lenguajes regulares y expresiones regulares

Sea S un alfabeto. El conjunto de los lenguajes regulares sobre S se define recursivamente como sigue:

1. Æ es un lenguaje regular

2. {e} es un lenguaje regular

3. Para todo a Î S {a} es un lenguaje regular

4. Si A y B son lenguajes regulares, entonces A È B, A • B , A* son lenguajes regulares

5. Ningún otro lenguaje sobre S es regular.

Ejemplo

Por ejemplo. El lenguaje de todas las cadenas sobre {a, b, c} que no tienen ninguna subcadena ac es un lenguaje regular, y puede expresarse por

A = {c}* ({a} È {b}{c}*)*

Simplificación

Se puede simplificar la notación mediante el uso de expresiones regulares. Las equivalencias son:

a È b denota {a} È {b}

ab denota {ab}

a* denota {a}*

a+ denota {a}+

Ejemplo: A = {c}* ({a} È {b}{c}*)* = c* (a È bc*)*

Expresiones regulares

Los operadores tienen precedencia (*, • , È). Entonces, una expresión regular sobre el alfabeto S, es

1. Æ y e son expresiones regulares.

2. a es una expresión regular para todo a Î S.

3. Si r y s son expresiones regulares, entonces r È s, r • s , r* también lo son.

4. Ninguna otra secuencia de símbolos es una expresión regular.

Equivalencia de expresiones regulares

Dos expresiones regulares pueden ser equivalentes, es decir, generan el mismo lenguaje.

La expresión (a*b)* es equivalente a eÈ (aÈb)*b.

Ambos generan e o cadenas de aes y bes terminadas en b.

La expresión

ab È eÈ (aÈb)*b

Es equivalente a

ab È (a*b)*

Reglas para expresiones regulares

1. r È s = s È r.

2. r È Æ = r = Æ È r.

3. r È r = r.

4. (r È s) È t = r È (s È t).

5. er = re = r.

6. Ær = rÆ = Æ.

7. (rs)t = r(st).

8. r(s È t) = rs È rt y (r È s)t = rt È st.

9. r* = r** = r*r* = (e È r)* = r*(r È e) = (r È e)r* = e È rr*.

10. (r È s)* = (r* È s*)* = (r*s*)* = (r*s)*r* = r*(sr*)* .

11. r(sr)* = (rs)*r.

12. (r*s)* = e È (r È s)*s.

13. (rs*)* = e È r(r

...