Tres lenguajes regulares e introducción a BNF.
Un lenguaje formal es un conjunto de palabras. Los LFs más simples son los lenguajes regulares, que tienen gran importancia en el diseño de los lenguajes de programación: los identificadores, las palabras reservadas, las constantes numéricas, los operadores y los caracteres de puntuación constituyen diferentes lenguajes regulares.
En el capítulo anterior hemos visto la Jerarquía de Chomsky y, con ella, los cuatro tipos de Lenguajes Formales existentes y las GFs que los generan. Por el momento, y solo para simplificar el análisis, distinguiremos dos clases de LFs: lenguajes regulares y lenguajes no regulares (que agrupa a los lenguajes Tipo 2, Tipo 1 y Tipo 0).
Todos los lenguajes ejemplificados en el capítulo 1 son Lenguajes Regulares.
Si un LF es finito, entonces siempre es un lenguaje regular (más adelante veremos porqué). En cambio, si un LF es infinito, entonces puede ser un Lenguaje Regular o un Lenguaje No Regular.
Solo a modo de presentación general, veamos ejemplos de los tres casos descriptos en las dos frases anteriores: lenguaje finito (es un LR), lenguaje infinito regular y lenguaje infinito no regular. Los “porqué” serán conocidos más adelante.
L1 = {anbn / 1 ≤ n ≤ 4} es un lenguaje finito y, por lo tanto, es un LR constituído por las cuatro palabras descriptas por comprensión.
El lenguaje “Todas las palabras formadas por una o más aes” es un LR infinito. Este lenguaje se puede escribir así: L2 = {an / n ≥ 1}.
Normalmente, para determinar cuándo un lenguaje infinito es Regular se requieren otras herramientas vinculadas con los Lenguajes Formales. Así, una primera definición es:
Un lenguaje es Regular si existe una gramática regular que lo genere (ver capítulo 2).
Otra definición es:
Un lenguaje es Regular si se puede representar mediante una expresión regular (se describe en el próximo capítulo).
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.
