Lenguajes regulares

Lenguaje Regular: Un lenguaje Regular es aquel que puede ser procesado por un Automata de Estados Finitos.
Un lenguaje regular es un tipo de lenguaje formal que satisface las siguientespropiedades:
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:
unagramática regular
una gramática de prefijos
Es descrito por:
una expresión regular
Para situar los lenguajes regulares en la jerarquía de Chomsky hay que notar que todo lenguaje regular es tambiénun 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.
Hay dos aproximaciones puramente algebraicas para definir lenguajes regulares. Si Σ es unalfabeto 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) esregular. 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 ∈ Lpara 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 deterministamínimo que reconocerá L.
Lenguajes regulares
Los lenguajes regulares constituyen el menor conjunto de lenguajes sobre S que es cerrado con respecto a las operaciones de concatenación, unión ycerradura de Kleene.
Además contienen el lenguaje vacío Æ y los lenguajes unitarios ā para aÎ S.
Desde el punto de vista práctico se utilizan como la base para la construcción de analizadores léxicos...