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 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 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é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.
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 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 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; si este es el caso, este número es igual al número de estados del autómata determinista mí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 y cerradura 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 (scanners).
Def.- Sea S un alfabeto. El conjunto de los lenguajes regulares sobre S se define recursivamente así: nÆ es un lenguaje regular. nē es un lenguaje regular. nPara toda aÎS, ā es un lenguaje regular. nSi A y B son lenguajes regulares, entonces AÈB, AB y A* son lenguajes regulares. nNingún otro lenguaje sobre S es regular.
Ejemplos de Lenguajes regulares Ej.- Dado S={a,b}, las siguientes afirmaciones son ciertas:
nÆ y ē son lenguajes regulares. nā y {b} son lenguajes regulares. n{a,b} es regular porque es la unión de ā y {b}. n{ab} es regular. n{a,ab,b} es regular. nai es regular. naibj es regular. n(ab)i es regular.
Ej.- ¿El lenguaje de todas las cadenas sobre {a,b,c} que no tienen ninguna subcadena ac es un lenguaje regular? nSi A es el lenguaje buscado, éste se podrá construir a partir de los lenguajes ā,{b},{c}, Æ y ē.
nSi w es una cadena perteneciente a A, entonces w comienza con 0 o más c’s.
nSi suprimimos este símbolo al inicio, obtenemos una subcadena w’ que no empieza por ningún caracter c.
nw’ estará formada por a’s, b’s y c’s, en las cuales las c’s siguen a las b’s. De hecho no puede haber ningún bloque de c’s al principio de w’. Es decir: ww’Î(āÈ{b}{c}*)* wy por tanto wÎ{c}* (āÈ{b}{c}*)* wde lo cual se obtiene: A Í {c}* (āÈ{b}{c}*)*
nPara probar la otra inclusión, si u es una cadena que tiene una subcadena ac entonces: wuÏ{c}* (āÈ{b}{c}*)*
ya que no hay forma de que una c pueda seguir una a.
Por tanto:
{c}* (āÈ{b}{c}*)* Í A
Informacion del instituto tecnologico de villa La Venta, carrera: ing. en sistemas computacionales
