Fundamentos de Gramáticas Formales y Autómatas de Estado Finito

Notación de Backus-Naur (BNF)

La notación de Backus-Naur (BNF) es un metalenguaje utilizado para expresar gramáticas libres de contexto; es decir, una manera formal de describir lenguajes formales. El BNF se emplea extensamente como notación para las gramáticas de los lenguajes de programación, sistemas de comandos y protocolos de comunicación, así como para representar partes de las gramáticas de la lengua natural.

Formas Normales en Gramáticas

Forma Normal de Chomsky (CNF o FNCH)

Cualquier lenguaje libre de contexto sin ε es generado por una gramática en la que todas las producciones siguen estas formas:

• A → a
• A → BC (con B, C ∈ V)
• S → ε

Pasos para la conversión a FNCH:

• Eliminación de símbolos no generadores.
• Eliminación de símbolos inalcanzables.
• Eliminación de producciones ε (épsilon).

Forma Normal de Greibach (FNG)

Una gramática está en FNG si cumple las siguientes condiciones:

• La variable inicial no es recursiva (no se llama a sí misma).
• La gramática no contiene variables inútiles.
• La gramática no contiene producciones ε.

Autómatas Finitos con Salida

Máquina de Moore

En la Máquina de Moore, la salida depende exclusivamente del estado en que se encuentra el autómata. Dicha salida se produce una vez y, cuando se llega a otro estado (o al mismo) por efecto de una transición, se genera el símbolo de salida asociado al estado de destino.

Se representan gráficamente como cualquier AFD, añadiendo al lado de cada estado la salida asociada (una cadena de caracteres). Su definición formal es un séxtuplo (K, Σ, Γ, δ, λ, q₀), donde:

• K, Σ y δ son equivalentes a los de un AFD.
• q₀ es el estado inicial.
• Γ es el alfabeto de salida.
• λ es una función de K a Γ*, que obtiene la salida asociada a cada estado.

Máquina de Mealy

La Máquina de Mealy es un tipo de máquina de estados finitos que genera una salida basándose en su estado actual y en una entrada. Esto implica que el diagrama de estados incluirá tanto señales de entrada como de salida para cada línea de transición.

A diferencia de la máquina de Moore, donde la salida depende solo del estado actual, en la de Mealy las transiciones tienen una entrada asociada. Su definición formal es un séxtuplo (K, Σ, Γ, δ, λ, q₀), donde todos los componentes tienen el mismo significado que en la máquina de Moore, a excepción de λ, que es una función λ: K × Σ → Γ*. Es decir, toma un elemento de K × Σ (un estado y un carácter de entrada) y produce una palabra formada por caracteres de Γ.