Copia - 5.3 Forma Normal de Chomsky

2025

Forma Normal de Chomsky

Lenguajes y Autómatas I

Introducción

Toda gramática libre de contexto 𝐺=(𝑁′,𝑇′,𝑃′,𝑆′)que no genere la palabra vacía puede transformarse en una gramática equivalente 𝐺^′=(𝑁′,𝑇′,𝑃′,𝑆′ )que esté en Forma Normal de Chomsky (FNC). Esto significa que cualquier gramática de este tipo puede reescribirse cumpliendo las reglas de la FNC, lo que facilita el análisis sintáctico y el diseño de algoritmos de reconocimiento, ya que en FNC las producciones tienen una forma estandarizada y más sencilla de manipular computacionalmente.

Pasos para la la transformación de una gramática a la FNC

Paso 1 – Eliminar reglas unitarias Una regla unitaria es cuando un No Terminal deriva en otro No Terminal que finalmente lleva a un Terminal (ej: A → X, X → z). Esto es redundante, por lo que se eliminan para simplificar la gramática.

Paso 2 – Eliminar reglas no productivas Son reglas con No Terminales que nunca producen cadenas válidas desde el símbolo inicial (ej: W → X, pero W nunca se alcanza desde el símbolo principal). Estas reglas se eliminan porque no aportan nada al lenguaje. ⚠️ Nota: En algunos programas este paso no se hace automáticamente, por lo que el usuario debe asegurarse de no introducir reglas improductivas.

Paso 3 – Dar formato a Forma Normal de Chomsky (FNC) La FNC sigue dos reglas:

1. Un No Terminal solo puede derivar en dos No Terminales.
2. Un No Terminal solo puede derivar en un Terminal.

Ejemplo simplificado: A → cB+ no cumple con la FNC. Se crean nuevos No Terminales para separar terminales y cumplir las reglas: A → ZY Z → c Y → BX X → + B → q Así la gramática queda en FNC correcta.

Diagrama de Sintaxis

Introducción

Los diagramas de sintaxis constituyen un mecanismo gráfico mediante el que aproximar, por refinamientos sucesivos, el lenguaje admisible por una gramática. A grandes rasgos, un diagrama de sintaxis es un grafo dirigido en el que los nodos representan los símbolos terminales y no terminales de la gramática, y los arcos expresan las secuencias en que pueden combinarse tales símbolos para formar frases aceptables según la gramática.

• Cada diagrama de sintaxis representa un símbolo no terminal (que se puede expandir), de manera que la gramática completa estará formada por tantos diagramas distintos e interrelacionados como no terminales se quieran incluir en su descripción.
• Los símbolos terminales (palabras o tokens) se dibujan como círculos o elipses etiquetadas con el nombre del token, mientras que los no terminales que aparecen en un grafo se dibujan como rectángulos etiquetados con su nombre correspondiente.
• Todo diagrama posee un punto de entrada (generalmente situado a la izquierda) y un punto de salida (a la derecha), y que están representados por un arco sin origen y un arco sin destino respectivamente.

Se ilustran los diagramas que resultan de la traducción de conjuntos de producciones típicos, que son por lo general, todas las producciones que aparecen en el lado derecho de algún enunciado BNF (Backus Normal Form).

Eliminación de Ambigüedad

Introducción

Una gramática es ambigua si una misma cadena puede generar más de una estructura. La ambigüedad puede darse en la gramática o en el lenguaje. Una gramática ambigua puede, en algunos casos, sustituirse por otra no ambigua que genere el mismo lenguaje.

• Un lenguaje inherentemente ambiguo es aquel cuyas gramáticas son siempre ambiguas.
• No existe algoritmo que determine de forma general si una gramática es ambigua

Ejemplo

Exp es una GLC

• Gexp = ({E}, {+, *, (, ), 1,..., 9}, E, P)
• donde P = {E → E + E | E * E | (E) | 1 |...| 9}

Una expresión ambigua:

• E+E*E

Dos derivaciones:

• E ⇒ E+E ⇒ E+E*E
• E ⇒ E*E ⇒ E+E*E

¡Son iguales!

La expresión final es la misma:

• E ⇒ * E+E*E
• E ⇒ * E+E*E

Pero las derivaciones son diferentes:

• E ⇒ E+E ⇒ E+E*E
• E ⇒ E*E ⇒ E+E*E

A cada derivación le corresponde una estructura sintáctica: Derivaciones diferentes pueden generar la misma estructura (para la misma cadena) La ambigüedad surge cuando derivaciones diferentes generan estructuras diferentes (para la misma cadena).

La expresión final es la misma: E ⇒ * E+E*E E ⇒ * E+E*ESus estructuras sintácticas son diferentes:

La expresión final es la misma: E ⇒ * E+E*E E ⇒ * E+E*ESus estructuras sintácticas son diferentes: La ambigüedad surge cuando hay más de una estructura sintáctica para la misma expresión.

¡GRACIAS!

2025