Lenguajes regulares

Unidad II: Lenguajes Regulares

Un lenguaje regular es un tipo de lenguaje formal que satisface las siguientes propiedades:
Puede ser reconocido por:
* un autómata finito determinista
* un autómata finito no determinista
* un autómata finito alterno
* una máquina de Turing de solo lectura
Es generado por:
* una gramática regular
* una gramática deprefijos
Es descrito por:
* una expresión regular


* Lenguajes regulares sobre un alfabeto
Un lenguaje recursivo sobre un alfabeto Σ dado se define recursivamente como:
* El lenguaje vacío es un lenguaje regular.
* El lenguaje cadena vacía {ε} es un lenguaje regular.
* Para todo símbolo a Σ {a} es un lenguaje regular.
* Si A y B son lenguajes regularesentonces A B (unión), A•B (concatenación) y A* (clausura o estrella de Kleene) son lenguajes regulares.
* Si A es un lenguaje regular entonces (A) es el mismo lenguaje regular
* No existen más lenguajes regulares sobre Σ.
Todo lenguaje formal finito constituye un lenguaje regular. Otros ejemplos típicos son todas las cadenas sobre el alfabeto {a, b} que contienen un número par de aes oel lenguaje que consiste en varias aes seguidas de varias bes.
Si un lenguaje no es regular requiere una máquina con al menos una complejidad de Ω(log log n) (donde n es el tamaño de la entrada). En la práctica la mayoría de los problemas no regulares son resueltos con una complejidad logarítmica.
Un lenguaje formal infinito puede ser regular o no regular. El lenguaje L = {an, n > 0} esregular porque puede ser representado, por ejemplo, mediante la expresión regular a+. El lenguaje L= {an bn, n > 0} es un lenguaje no regular dado que no es reconocido por ninguna de las formas de representación anteriormente enumeradas.


* Propiedades de cerradura

Los lenguajes regulares son cerrados con las siguientes operaciones, de modo que si L y P son lenguajes regulares lossiguientes lenguajes también serán regulares:
* El complemento de L
* La clausura o estrella de Kleene L* de L
* El homomorfismo φ(L) de L
* La concatenación L'P de L y P
* La unión L ∪ P de L y P
* La intersección L ∩ P de L y P
* La diferencia L \ P de L y P
* La reversa LR de L

* Decidir cuándo un lenguaje es regular

Para situar loslenguajes regulares en la jerarquía de Chomsky hay que notar que todo lenguaje regular es también un lenguaje independiente de contexto, aunque la afirmación contraria no es cierta, por ejemplo: el lenguaje que contiene el mismo número de aes y de bes es independiente de contexto pero no regular. Para probar que un lenguaje de este tipo no es regular se usa el teorema de Myhill-Nerode por ejemplo.
Haydos aproximaciones puramente algebraicas para definir lenguajes regulares. Si Σ es un alfabeto finito y Σ* es un monoide libre consistente en todas las cadenas sobre Σ, f: Σ* → M es un monoide simétrico donde M es un monoide finito y S es un subconjunto de M entonces el conjunto f-1(S) es regular. Todo lenguaje regular se presenta de esta manera.
Si L es un subconjunto de Σ*, se define larelación equivalente ~ en Σ* de la siguiente manera: u ~ v significa
uw ∈ L si y solo si vw ∈ L para todo w ∈ Σ*
El lenguaje L es regular si y solo si el número de clases de equivalencia de ~ es finito; si este es el caso, este número es igual al número de estados del autómata determinista mínimo que reconocerá L.






2.1 Autómatas finitos
Un automata finito es un modelo matematicode una maquina que acepta cadenas de u lenguaje definido sobre un alfabeto A. Consiste en un conjunto finito de estdos y un conjunto de transciciones entre estos estados que dependen de los simbolos de la cadena de entrada. El automata finito acepta una cadena x si la secuencia de transciciones correspondiente a los simbolos de x conduce desde el estado inicial a un estado final.
* Si para...