Fundamentos de Lenguajes Formales y Autómatas Finitos: Definiciones Clave

Conceptos Fundamentales de Lenguajes Formales

Cadena de Caracteres (String)

Una cadena de caracteres, palabra o frase (string) es una secuencia ordenada de una longitud arbitraria (aunque finita) de elementos que pertenecen a un cierto alfabeto. En general, una cadena de caracteres es una sucesión de letras, números u otros signos o símbolos.

En matemáticas, es habitual usar las letras w, x, y, z para referirnos a las cadenas. Desde el punto de vista de la programación, una cadena podrá estar formada por cualquier combinación finita de todo el juego de caracteres disponibles.

Alfabeto

El alfabeto es un conjunto ordenado de las letras de un idioma; es la agrupación con un orden determinado de las grafías utilizadas para representar el lenguaje que sirve como sistema de comunicación. En matemáticas, es un conjunto ordenado finito de símbolos.

Lenguaje Formal

Un lenguaje formal es un conjunto de palabras (cadenas de caracteres) de longitud finita formadas a partir de un alfabeto finito. El nombre «lenguaje» se justifica porque las estructuras que con este se forman tienen reglas (gramática) e interpretación semántica (significado).

Especificación de Lenguajes Formales

Los lenguajes formales se pueden especificar de una amplia variedad de formas, como por ejemplo:

• Cadenas producidas por una gramática formal.
• Cadenas producidas por una expresión regular.
• Cadenas aceptadas por un autómata, tal como una máquina de Turing.

Operaciones Fundamentales

Expresión Regular (Patrón)

La expresión regular, también llamada patrón, es una forma de representar a los lenguajes regulares. Se construye utilizando caracteres del alfabeto sobre el cual se define el lenguaje, específicamente mediante la unión, la concatenación y la cerradura de Kleene.

Concatenación

Es la operación por la cual dos caracteres se unen para formar una cadena de caracteres o un string. También se pueden concatenar dos cadenas de caracteres o un carácter con una cadena para formar una cadena de mayor tamaño.

Cerradura de Kleene (A*)

Si A es un lenguaje sobre un alfabeto, la cerradura estrella se define de la siguiente manera: A* = ∪_n=0 Aⁿ. Esto significa que el símbolo puede aparecer en una cadena 0, 1, 2, ..., o infinitas veces.

Cerradura Positiva (A⁺)

Se define de la siguiente manera: A⁺ = ∪_n=1 Aⁿ. Esto indica que el símbolo al que sigue el signo deberá aparecer al menos una vez.

Autómatas Finitos y sus Aplicaciones

Autómatas Finitos

El autómata finito es un modelo matemático de un sistema de entradas y salidas discretas. El sistema puede estar en cualquiera de un número finito de configuraciones o estados. El estado del sistema resume la información concerniente a entradas anteriores y que es necesaria para determinar el comportamiento del sistema para entradas posteriores. Se dice que un lenguaje es regular si es aceptado por un autómata finito.

Autómata Finito Determinista (AFD)

Un Autómata Finito Determinista (AFD) es un conjunto de estados y un conjunto de transiciones de estado a estado que se dan sobre símbolos de entrada tomados de un alfabeto. Para cada símbolo de entrada existe solo una transición a partir de cada estado. Se tiene un estado inicial y uno o más estados de aceptación. Un AFD está asociado a un grafo dirigido conocido como diagrama de transiciones.

Definición Formal de un AFD

Un AFD se define como una quíntupla:

AFD = (Q, Σ, δ, q₀, F)

Donde:

• Q: Es el conjunto finito de estados.
• Σ: Es el alfabeto de entrada finito.
• δ: Son las funciones de transición o tabla de transiciones.
• q₀: Es el estado inicial.
• F: Es el conjunto de estados finales (o de aceptación).

Aplicaciones en la Computación

Los autómatas finitos se encuentran en el nivel más bajo de la jerarquía de máquinas y lenguajes.

Una de sus aplicaciones principales es la construcción de compiladores. Por ejemplo, un compilador debe ser capaz de reconocer cuáles son las cadenas o símbolos del programa fuente que deben considerarse como representaciones de objetos individuales. Esto incluye:

• Nombres de variables.
• Constantes numéricas.
• Palabras reservadas.

Esta tarea de reconocimiento de patrones es manejada por el *analizador léxico* del compilador.