Lenguajes naturales

Lenguajes sobre alfabetos
Todos los lenguajes ∑ son sub-lenguajes del lenguaje universal ∑*, tiene sentido determinar primero cuantos sub-lenguajes tiene ∑* para elalfabeto ∑ en particular. Comenzaremos estudiando el propio

Ejemplo
Consideremos ∑ = { a, b } para todo numero natural n
Por conveniencia numeraremos ԑ como 0, despues laspalabras de longitud 1 depues de longitud n , n+1, etc

Teorema : PARA TODO ALFABETO ∑, ∑* ES INFINITO NUMERABLE

Teorema : EL CONJUNTO DE TODOS LOS LENGUAJES SOBRE ∑NO ES NUMERABLE Demostración

Lenguajes regulares y expresiones regulares
Definición : SEA ∑ UN ALFABETO. EL CONJUNTO DE LOS LENGUAJES REGULARES SOBRE ∑ SE DEFINENRECURSIVAMENTE
a) b) c) d) ɸ es un lenguaje regular {ԑ} es un lenguaje regular Para todo a є ∑, {a} es un lenguaje regular Si A y B son lenguajes regulares, entonces AᴗB, A·B yA* son lenguajes regulares e) Ningún otro lenguaje sobre ∑ es regular

Ejemplo
Dado ∑ = { a, b }, las siguientes afirmaciones son ciertas:
ɸ y {ԑ} son lenguajesregulares {a} y {b} son lenguajes regulares {a, b} es regular por que es la unión de {a} y {b} {ab} es regular {a, ab, b} es regular { | i >= 0} es regular { | i >= 0 y j>=0} esregular { | i >= 0} es regular

Teorema : SEA r, t Y t EXPRESIONES REGULARES SOBRE EL MISMO ALFABETO ∑ ENTONCES:
1. 2. 3. 4. rᴗs= sᴗr rᴗɸ=r=ɸᴗr r ᴗ r= r (r ᴗ s) ᴗ t = rᴗ (s ᴗ t)

5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15.

rԑ=ԑr=r rɸ=ɸr=ɸ (r s) t = r (s t) r (s ᴗ t) = r s ᴗ r t y (r ᴗ s) t = r t ᴗ s t r* = r** = r*r* =(ԑᴗr)*= r*(rᴗԑ) =(rᴗԑ) r* = ԑᴗr r* (r ᴗ s)* = (r* ᴗ s*)* = (r*s*)*= (r*s*)r* = r(sr*)* r(sr)* = (rs)* r (r*s)* = ԑ ᴗ (r ᴗs)* s (rs*)* = ԑ ᴗ r(r ᴗ s) s(r ᴗ ԑ)* (r ᴗ ԑ) ᴗ s = sr* rr* = r*r