Introducción

Un lenguaje regular es un tipo de lenguaje formal. Son aquellos ubicados en el núcleo de la jerarquía de Chomsky, también, son los más simples y tienen el objetivo de llevar a cabo técnicas de reconocimiento de patrones. Estas técnicas son llevadas a cabo en una fase del compilador que se llama el análisis lexicográfico o lexer.

La importancia de los lenguajes regulares con respecto a los lenguajes de programación es que permiten realizar reconocimiento de identificadores, palabras reservadas, constantes numéricas, operadores y los caracteres de puntuación.

Todos los lenguajes formales que son finitos, son regulares. Mientras que los lenguajes formales infinitos pueden o no ser lenguajes regulares.

Gramática Formal (GF)

Las gramáticas formales son descripciones estructurales de las sentencias de los lenguajes, tanto formales (lenguajes de programación) como naturales (humanos). Describen "cómo" se pueden generar las palabras de un lenguaje.

Son un conjunto de producciones (reglas de reescritura) que se aplican para obtener cada una de las palabras del lenguaje formal, el cual a su vez, está definido sobre un alfabeto Σ.

Por ejemplo:

1. Tengo un lenguaje L1 formado por las palabras L1 = {a, aa}, entonces mi gramática necesitaría dos producciones o reglas:
   1. S → a “S derivando en a”
   2. S → aa “Se derivando en aa”

Definición formal de una gramática

Toda gramática formal G, se define como una cuádrupla G = (ΣT, ΣN, S, P) donde:

1. ΣT: El alfabeto de símbolos terminales. Es el conjunto finito de símbolos terminales del alfabeto sobre el cual se construye el lenguaje formal que es generado por la gramática descripta. Ejemplo: ΣT = {0, 1}
2. ΣN: El alfabeto de símbolos no terminales. Conjunto finito de símbolos especiales denominados no terminales que permiten representar subconjuntos del lenguaje o estados intermedios de la generación de las palabras del lenguaje, cumpliéndose:
   • Σ = ΣT U ΣN
   • ΣT ∩ ΣN = {}
3. S: El símbolo inicial (start) o axioma o símbolo distinguido. Es un símbolo no terminal especial. S ∈ ΣN (S pertenece al alfabeto de símbolos no terminales). A partir de S siempre debe comenzar a aplicarse las producciones que generan todas las palabras de un determinado lenguaje formal. Algunos autores consideran que el símbolo S no puede aparecer en la derecha de una producción.
4. P: El conjunto finito no vacío de producciones. Permiten generar palabras a partir de S. Cada producción tiene como única restricción que en la parte izquierda debe haber al menos un símbolo no terminal. Es decir, P = {(xAy -> v) / v, x, y ∈ Σ* , A ∈ ΣN} Ejemplo: A -> 1B1 | 0B0 B -> A | 1 | 0 | λ

Producciones

Una producción es una regla de reescritura donde decimos que : α → β se lee: “alfa deriva/reescribe/produce a beta”. Están compuestas por 3 partes:

1. Un lado izquierdo.
2. Un lado derecho.
3. La flecha, que indica que el lado izquierdo de la producción “produce” (o “es reemplazado por” o “equivale a”) el lado derecho.

Ejemplo

En el siguiente ejemplo tenemos una gramática donde podemos apreciar las producciones que la conforman e identificamos los demás elementos que forman parte de ella: