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.

En la práctica la mayoría de los problemas no regulares son resueltos con una complejidad logarítmica.

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.

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: Dados dos autómatas finitos deterministas A y B, como consecuencia de las propiedades de clausura, los siguientes problemas son también decidibles para cualquier autómata finito determinista A y B, con LA y LB los lenguajes que son aceptados por los autómatas respectivamente: 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 que contiene el mismo número de 'a's y de 'b's es libre de contexto pero no regular.

Hay dos aproximaciones puramente algebraicas para definir lenguajes regulares.