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).
