• Author / Uploaded
• Adrian Martinez

Citation preview

Lenguajes Regulares Casos base: {E},{},{a} para toda cadena con 1 simbolo son Regulares Si L1 y L2 son lenguajes regulares entonces entonces L1 u L2 es un Lenguaje Regular L1.L2 es un lenguaje regular L1* es un lenguaje regular (Estas son las 3 operaciones fundamentales) -.-.-..-.-.-.-.-.-.-.-.-.-.-.-.-.-.--.-.-.-.-.-.-.-.-.-.-.-.-. Sea "Sigma"(alfabeto) = {a,b} L1 = {} L2 = {E} L3 = {} L4 = {a} L5 = {b} L6 = {aa,ab} L5* = {E,b,bb,bbb,bbbb,bbbbb,...} L6* = {E,aa,ab,aaaa,aaab,abaa,abab,...} .-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.--.-.-.-.-.--.-.-.-.-. Todo lenguaje finito es regular Todo lenguaje infinito regular es resultado de una cerradura de kleene "Sigma"* es regular .-.-..-.-.--.-.-.-.-.---...---...---.-.-.---.-.-.---...--..--.-.-.---.-.-.---.--.-. -.--.--.."Sigma" = {0,1,2} L1 = {E} L2 = {} L3 = {0} L4 = {1} L5 = {2} L6 = {0,1} L7 = {0,2} L8 = {0,1,2} L9 = {E,1,11,111,...} L10 ={E,0,00,000,...} -.-..-.--.-.-.-.-.-..-.-.-.--.--.-.-.--.-.-.--.-.-.-.-.-.-.-.-.---.-.-.--.---.-.--. --.-.-.-.--.---.-Propiedades de los Lenguajes Regulares Sea L1, L2 lenguajes regulares. *

L1' es regular

* * *

L1 n L2 es regular = (L1' u L2')' L1 - L2 es regular = L1 n L2' L1^R es regular

-.-.-.--.-.-.-.--.-.-.-...-.-.--.-.-.-.-.-.--.-.--.-.-.-.-.-.--.-.-.-.-.-.--..--.-. -.-.-.-.-.-.-.-.-.-.-. Expresiones Regulares Se usan para eliminar la notacion de conjuntos y nos permiten manipular los LR de manera mas sencilla utilizando las propiedades algebraicas con las 3 operaciones basicas Elimina notacion de conjunto.

(no llaves)

Caso base. "Vacio",E,a son Expresiones Regulares Si r y s son E.R. r u s es E.R. rs es E.R. r* es E.R. -.-.-..-.-.-.-.-.-.--.--.-.-.---.-.-.-.-.-.-..-.-.-.-.-.-.-.-.-.-.-.-.-.-.....-.--. -.-.Coma se remplaza por u L = (a* . b u c) a* -> a*b -> a*b u c