Lenguajes Y Jerarquías

Lenguaje regular
Un lenguaje regular es un tipo de lenguaje formal que satisface las siguientes propiedades:
Los lenguajes más sencillos que se considerarán son los lenguajes regulares, es decir, los que se pueden generar a partir de los lenguajes básicos, con la aplicación de las operaciones de unión, concatenación y * de Kleene un número finito de veces.
Puede ser reconocido por:un autómata finito deterministaun autómata finito no deterministaun autómata de pilaun autómata finito alterno
una máquina de Turing de solo lectura
Es generado por:
una gramática regularuna gramática de prefijos
Es descrito por:
una expresión regularÍndice
  [ocultar] 
1 Lenguajes regulares sobre un alfabeto2 Propiedades de cierre3 Decidir cuándo un lenguaje es regular4 Lenguajes finitos5 EnlacesexternosLenguajes regulares sobre un alfabeto
Un lenguaje regular 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 regulares entonces A ∪ B (unión), A•B (concatenación) y A* (clausura o estrella de Kleene) son lenguajesregulares
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 o el lenguaje que consiste en varias aes seguidas de varias bes.
Si un lenguaje no es regular requiere unamá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} es regular 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 cierre
Los lenguajes regulares son cerrados con las siguientes operaciones, de modo que si L y P son lenguajes regulares los siguientes 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
El reverso LR de L
Decidir cuándo un lenguaje es regular
Para situar los lenguajes regulares en la jerarquía de Chomsky hay que notar que todo lenguaje regular es también un lenguaje libre de contexto, aunque la afirmación contraria no es cierta, por ejemplo: el lenguaje quecontiene el mismo número de aes y de bes es libre de contexto pero no regular. Para probar que un lenguaje de este tipo no es regular se usa el teorema de Myhill-Nerode, o el lema de bombeo por ejemplo.
Hay dos 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 monoidesimé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 la relació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; sieste es el caso, este número es igual al número de estados del autómata determinista mínimo que reconocerá L.
Lenguajes finitos
Un subconjunto especial de los lenguajes regulares es el de los lenguajes finitos, aquellos que solo contienen un número finito de palabras. Estos son lenguajes obviamente regulares y uno podría crear expresiones regulares que serían la unión de todas las...