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

...