Tres lenguajes regulares e introducción a BNF.
Una tercera definición es:
Un lenguaje es Regular si puede ser reconocido por un autómata finito (se presenta en el capítulo 5).
Nota 1: Obviamente, todo lenguaje que no es Regular es un Lenguaje No Regular.
Sea el lenguaje: “Todas las palabras que comienzan con una secuencia de una o más aes y terminan con una secuencia de bes cuya cantidad es igual a la cantidad de aes que las preceden”. Una representación más precisa de este lenguaje es: L3 = {anbn / n ≥ 1}.
Sus tres palabras de menor longitud son: ab, aabb y aaabbb.
Note que el mismo supraíndice (n) es utilizado para indicar la cantidad de aes y la cantidad de bes presentes en cada palabra; de esta forma se representa la igualdad entre las cantidades de ambos símbolos.
Este lenguaje es infinito y No Regular porque no podremos representarlo mediante una Expresión Regular, y no podremos construir un Autómata Finito que lo reconozca, y no podremos elaborar una Gramática Regular que lo genere.
Ejercicio: Trate de construir una GR que genere el LF del Ejemplo 3.
En este capítulo presentamos a los LRs a través de diversos ejemplos y algunas acotaciones importantes. Por de pronto, como ya hemos visto en los Ejemplos 1 y 2, los LRs pueden ser finitos o infinitos. He aquí otros ejemplos:
El lenguaje: “Todas las palabras formadas solo por aes, cuyas longitudes están entre 1 y 1000” es un lenguaje finito y, por lo tanto, es un Lenguaje Regular.
Este lenguaje puede ser descripto por comprensión, así: L4 = {an / 1 ≤ n ≤ 1000} (el supraíndice n indica la cantidad de veces que se repite el carácter a).
Las tres palabras de menor longitud de este lenguaje son: a, aa, aaa.
Consideremos el lenguaje infinito definido de esta manera: L5 = {anbt / n ≥ 1, t ≥ 1}. Este lenguaje es Regular.
Las tres palabras de menor longitud de este lenguaje son: ab, abb, aab.
Observe que este lenguaje tiene cierta similitud con el lenguaje No Regular del Ejemplo 3, {anbn / n ≥ 1}, en cuanto a la ubicación de los caracteres que forman cada palabra, pero carece de la restricción que se refiere a la “igualdad de cantidades” entre el bloque de aes y el bloque de bes que debe tener toda palabra del lenguaje.
Se puede comprobar fácilmente que el lenguaje {anbt / n ≥ 1, t ≥ 1} contiene al lenguaje {anbn / n ≥ 1}.
Ejercicio: Construya una GR que genere el LR del Ejemplo 5.
Sea el lenguaje infinito: L6 = {(ab)n (cde)t az / n ≥ 1, t ≥ 1, z ≥ 1}. Este lenguaje también es Regular porque no existe relación entre las cantidades de los grupos que lo definen.
Algunas palabras de este lenguaje son:
si n = 3, t = 1, z = 1, la palabra es abababcdea
si n = 1, t = 4, z = 2, la palabra es abcdecdecdecdeaa.
El lenguaje: “Todos los números binarios que comienzan con una cantidad impar de 1s y terminan con un 0”, que por comprensión se escribe L = {12n+10 / n ≥ 0}, es un LR infinito. Las primeras tres palabras de este lenguaje son: 10, 1110, 111110.
Los lenguajes: “Todas las palabras de aes y bes que contienen el patrón aa” (como baabb), “Todas las palabras de aes y bes que no contienen el patrón aa” (como aba) y “Todas las palabras de aes y bes que terminan con aa o con bb” (como baa) son LRs.
En el próximo capítulo se introduce una noción muy importante: las expresiones regulares. El conocimiento de este tipo de expresiones es esencial para comprender mejor qué lenguajes son Regulares y cuáles no lo son.
