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:

Es generado por:

Es descrito por:

Lenguajes 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 AB (unión), AB (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 o el 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} 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.

Other Languages
فارسی: زبان منظم
hrvatski: Regularni jezik
日本語: 正規言語
한국어: 정규 언어
Nederlands: Reguliere taal
português: Linguagem regular
română: Limbaj regulat
српски / srpski: Regularni jezik
українська: Регулярна мова
中文: 正则语言