TEORÍA DE LA COMPUTACIÓN

Tema 02 – Gramáticas Formales

Profesor:
Mag. Ing. Pablo Pandolfo
Gramáticas Formales

● Gramática:

○ Intuitivamente es un conjunto de reglas para formar correctamente las

frases de un lenguaje.
○ Por ejemplo, gramática del castellano (o de cualquier idioma) nos
permite:
■ Identificar cuándo una frase es sintácticamente correcta.
● “Juan es un buen estudiante”.
● “Es un Juan estudiante buen”.
■ Generar todos las posibles frases sintácticamente correctas.
Gramáticas Formales

● Gramática Formal:

○ Son descripciones estructurales de las sentencias de los lenguajes,

tanto formales (lenguajes de programación) como naturales
(humanos).
○ Generan las palabras que forman un lenguaje formal definido sobre un
alfabeto Σ.
○ Describen “cómo” se pueden generar las palabras de un lenguaje.
○ Es un conjunto de producciones (reglas de reescritura) que se aplican
para obtener cada una de las palabras del lenguaje formal que la
gramática formal en cuestión genera.
Gramáticas Formales

● Ejemplo:

○ Sea el lenguaje L = {a}, formado por una sola palabra. Este lenguaje es
generado por una gramática con una única producción:
S -> a

○ Se lee “S produce a” o “S deriva a”.

Gramáticas Formales

● Producción:

○ Es una regla de reescritura formada por 3 partes:

■ el lado izquierdo,
■ el lado derecho, y
■ la flecha, que indica que el lado izquierdo de la producción
“produce” (o “es reemplazado por” o “equivale a”) el lado derecho.
α -> β
Gramáticas Formales

● Definición formal:

○ Toda gramática formal G, se define como una cuádrupla

G = (ΣT, ΣN, S, P)

○ donde:
■ ΣT : alfabeto de símbolos terminales.

■ ΣN : alfabeto de símbolos no terminales.

■ S : símbolo inicial (start) o axioma o símbolo distinguido.
■ P : conjunto finito no vacío de producciones.
Gramáticas Formales

● Definición formal:

■ ΣT :
● 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}
Gramáticas Formales

● Definición formal:

■ ΣN :
● 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 = {}
Gramáticas Formales

● Definición formal:
■ S:
● Símbolo inicial (start) o axioma o símbolo distinguido.
● Es un símbolo no terminal especial.
● S ∈ ΣN
● Desde el cual 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.
Gramáticas Formales

● Definición formal:
■ P:
● Conjunto finito de producciones (reglas de reescritura).
● 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 | λ
Gramáticas Formales

● Ejemplo:

VN = {S, T}
VT = {a, b}
S=S
P = {(S -> aT), (T -> a), (T -> b)}

L = {aa, ab}
Gramáticas Formales

● Ejemplo:
Gramáticas Formales

● Regla Compresora:

○ Aquella cuya parte derecha está formada por menos símbolos que la
parte izquierda:
α -> β
|β| < |α|

○ Transforma una palabra en otra de menor longitud.

○ Ejemplos:
■ 0C0 -> 1
■ A -> λ
Gramáticas Formales

● Jerarquía de Chomsky:

○ En 1956 y 1959, el lingüista norteamericano Noam Chomsky publicó

dos trabajos sobre los Lenguajes Naturales que, aplicados al área de
los Lenguajes Formales, produjeron lo que se conoce como Jerarquía
de Chomsky.

○ Establece una clasificación (según las restricciones o formatos que se

imponen a sus producciones) de cuatro tipos de gramáticas formales
que, a su vez, generan cuatro tipos diferentes de lenguajes formales.
Gramáticas Formales

● Jerarquía de Chomsky:
Gramáticas Formales

GRAMÁTICAS LENGUAJES
Gramática tipo 3 o Regular Lenguaje Regular
Gramática tipo 2 o Independiente Lenguaje Independiente (libre) de
(libre) de Contexto Contexto
(incontextuales)
Gramáticas tipo 1 o Dependiente Lenguaje Dependiente (sensible)
(sensible) de Contexto de Contexto
(contextuales)
Gramática tipo 0 o sin Lenguaje Recursivamente
restricciones (Irrestricta) Enumerable
Gramáticas Formales
Gramáticas Formales
Gramática Tipo 3 o Regulares
● Generan las palabras de los lenguajes regulares.
● Son las gramáticas más restrictivas.
● Si sus producciones tienen las siguientes restricciones:
○ el lado izquierdo debe tener un solo no terminal,
○ el lado derecho debe estar formado por un solo terminal, o un
no terminal seguido de un terminal.
○ el símbolo distinguido puede o no derivar a λ
Lineales por la izquierda
P={(S -> λ) | (A -> Bv) | (A -> v) / (A,B) ∈ ΣN, v ∈ ΣT}
Lineales por la derecha
P={(S -> λ) | (A -> vB) | (A -> v) / (A,B) ∈ ΣN, v ∈ ΣT}
Ejemplo 1: P = {(S -> C0), (S -> D1), (C -> 1), (D -> C1)}
Ejemplo 2: P = {(A -> 1B), (B -> 1), (B -> 0C), (B -> 1C), (C -> 1)}
Ejemplo 3: P = {(S -> λ}, (S -> aA), (A -> aB), (A -> a), (B -> aA)}
Ejemplo 4: P = {(S -> λ), (S -> Ca), (C -> Da), (C -> a), (D -> Ca)}
 Gramáticas Formales
Gramática Tipo 2 o Independientes (libre) de Contexto
● Generan las palabras de los lenguajes libres de contexto.
● Si sus producciones tienen las siguientes restricciones:
○ el lado izquierdo debe tener un solo no terminal,
○ el símbolo distinguido puede o no derivar a λ

P={(S -> λ) | (A -> v) / A ∈ ΣN, v ∈ Σ+}

Ejemplo 1: P = {(S -> λ), (S -> 01S1), (S -> 0S10), (S -> A1), (A -> 0S10)}
Ejemplo 2: P = {(A -> 1B1), (A -> 11), (B -> 1), (B -> 0)}
Ejemplo 3: P = {(S -> A), (A -> aAa), (A -> bAb), (A -> c)}
Ejemplo 4: P = {(S -> ABC), (S -> AC), (S -> BC), (S -> C), (A -> 0A1), (A ->
01), (B -> 1B2), (B -> 12), (C -> 3C), (C -> 3)}
● Estas GICs son de gran utilidad en la representación de la sintaxis de
los Lenguajes de Programación.
Gramáticas Formales

Gramática Tipo 1
● Si sus producciones tienen las siguientes restricciones:
○ |β| ≥ |α|.
○ el símbolo distinguido puede o no derivar a λ

P={(S -> λ) | (xAy -> xvy) / (A ∈ ΣN, (x,y) ∈ Σ*, v ∈ Σ+}

Ejemplo 1: P = {(S -> λ), (S -> 0A100), (0A1 -> 011), (0A0 -> 000)}
Ejemplo 2: P = {(A -> 1B1), (A -> 11), (1B1 -> 101), (1B1 -> 111)}
 Gramáticas Formales

Gramática Tipo 0
● En la parte izquierda tiene que haber al menos un símbolo no terminal.
● Respecto a las partes derechas de sus producciones no hay ningún tipo de
restricción.

P={(xAy -> v) / (v,x,y) ∈ Σ*, A ∈ ΣN}

Ejemplo 1: P = {(S -> 0), (0SA -> 0A10), (A -> 1), (A -> 1S0)}
Ejemplo 2: P = {(S -> A0), (A0 ->1B1), (1A -> 0B0), (B -> λ), (B -> 1), (B -> 0)}
Gramáticas Formales

● Derivación:

○ Es el proceso que permite obtener cada una de las palabras de un LF a

partir del axioma de una GF que lo genera y aplicando sucesivamente
las producciones convenientes de esa GF.

○ Existen diferentes formas de representar una derivación:

■ Derivación Horizontal.
■ Derivación Vertical.
Gramáticas Formales

● Derivación Horizontal:

○ Utilizando el símbolo => en cada paso de una derivación.

○ Ejemplo:

S => cAd => cabd

Gramáticas Formales

● Derivación Horizontal:

○ Ejemplo L = {anb / n > 0}

Producciones:
S -> aA
A -> aA
A -> b

Derivaciones:
S => aA => ab ab ∈ L
S => aA => aaA => aab aab ∈ L
S => aA => aaA => aaaA => aaab aaab ∈ L
Gramáticas Formales

● Forma sentencial:

○ w es forma sentencial si existe una derivación desde el axioma hasta

esa palabra; es decir, S -> w
○ Dada la gramática G:
A -> 1B1 | 0B0
B -> A | 1 | 0 | λ
○ Las siguientes son formas sentenciales:
■ 010: A -> 0B0 -> 010
■ 1A1: A -> 1B1 -> 1A1
■ 1001: A -> 1B1 -> 1A1 -> 10B01 -> 1001
Gramáticas Formales

● Sentencia:

○ w es sentencia si es forma sentencial y todos sus símbolos

pertenecen al alfabeto de símbolos terminales; es decir, S -> w, w ∈ ΣT*

○ Ejemplo: En el ejemplo anterior,

■ 010: SENTENCIA
■ 1A1: NO SENTENCIA
■ 1001: SENTENCIA
Gramáticas Formales

● Lenguaje generado por una gramática L(G):

○ Es el conjunto de todas las sentencias de la gramática; es decir, todas

las palabras que se pueden obtener a partir del axioma de la gramática
por la aplicación de derivaciones:

L(G) = {w ∈ ΣT* : S -> w}

○ Ejemplo:

L(G) = {cabd, cad}

Gramáticas Formales

● Derivación Vertical:

○ Árbol de derivación: permite mostrar gráficamente cómo se puede

derivar cualquier palabra de un lenguaje a partir del axioma de una
gramática que genera ese lenguaje.
○ Reemplazado un no terminal por su lado derecho para producir un
nuevo subárbol.
○ Son utilizados en la construcción de compiladores para representar el
análisis sintáctico de los programas fuente y sirviendo de base para la
generación de código.
Gramáticas Formales
● En los árboles de derivación:

○ El axioma se representa en la raíz del árbol.

○ Los nodos hojas del árbol son símbolos terminales de la gramática.
○ Los nodos intermedios (interiores) son símbolos no terminales de la
gramática.
○ Las derivaciones se representan creando tantos sucesores del
símbolo no terminal de la izquierda de las producciones como
símbolos (terminales y no terminales) aparezcan en la parte de las
producciones.
Gramáticas Formales
● En los árboles de derivación:

○ Para cada palabra del lenguaje generado por una gramática es posible
construir (al menos) un árbol de derivación en el cual cada hoja tiene
como rótulo uno de los símbolos de la palabra.
○ Ejemplo: suponer la siguiente gramática que describe la sintaxis de
una asignación simplificada para un lenguaje de programación “tipo
pascal”:
Gramáticas Formales
● En los árboles de derivación:
○ Suponer las palabras: A := A + B y C := D – E * F, las cuales pertenecen
a la gramática anterior, y cuyos árboles de derivación serían:
Gramáticas Formales

● Gramáticas equivalentes:

○ Dos gramáticas G y G’ son equivalentes si generan el mismo lenguaje,

es decir, si

L(G) = L(G’)

Ejemplo
G G’
S -> c A d S -> cabd
A -> ab S -> cad
A -> a
Gramáticas Formales
● Gramáticas ambiguas:

○ Una gramática es ambigua si tiene al menos una sentencia ambigua.

○ Una sentencia es ambigua si tiene más de una derivación o árbol de
derivación.
○ Un lenguaje es ambiguo si existe una gramática ambigua que lo
genera.
○ En algunos casos, dada una gramática ambigua, se puede encontrar
otra gramática que produzca el mismo lenguaje pero que no sea
ambigua.

Ejemplo
S -> 1 B Dos derivaciones para 11:
S -> 11 S => 1 B => 11
B -> 1 S => 11
Gramáticas Formales
● Gramáticas ambiguas:

○ Ejemplo: Suponer la siguiente gramática para una asignación

simplificada:
Gramáticas Formales
● Gramáticas ambiguas:

○ Ejemplo: Para la palabra J = 1 + 2 * 3, se tienen los siguientes árboles

de derivación:
Gramáticas Formales
● Gramáticas ambiguas:

○ En el caso de la gramática enunciada anteriormente se puede corregir

la ambigüedad considerando la precedencia de operadores, como se
mostró anteriormente:

AMBIGUA

NO
AMBIGUA
Gramáticas Formales
● Gramáticas ambiguas:

○ Ejemplo:
E -> E + E | E * E | num | id | (E)

○ Derivaciones para la palabra id1 + id2 * id3

■ Por la izquierda: E => E * E => E + E * E => id1 + E * E => id1 + id2 *
E => id1 + id2 * id3
■ Por la derecha: E => E * E => E * id3 => E + E * id3 => E + id2 * id3
=> id1 + id2 * id3
○ Se observa que la gramática es ambigua, para su implementación, es
necesario evitar la ambigüedad.
 Gramáticas Formales
● Gramáticas ambiguas:

○ Árboles sintácticos:
DERIVACIÓN POR LA DERIVACIÓN POR LA
IZQUIERDA DERECHA
E E

E * E E + E

E + E id3 id1 E * E

id1 id2 id2 id3

Gramáticas Formales
● Gramáticas ambiguas:

○ Si una gramática tiene alguna de estas características, se podrá

afirmar que es ambigua:
■ Gramáticas con ciclos:
S -> A | a
A -> S
■ Gramáticas con alguna regla de la forma:
E -> E …E
■ Gramáticas con reglas que ofrecen caminos alternativos entre dos
puntos:
S -> B | C
B -> C
Gramáticas Formales
● Gramáticas ambiguas:

○ Producciones recursivas en las que las variables no recursivas de la

producción puedan derivar a la palabra vacía. Por ejemplo:
S -> A B S | s
A -> a | λ
B -> b | λ
○ Símbolos no terminales que puedan derivar a la palabra vacía y a la
misma palabra de terminales, y que aparezcan juntas en la parte
derecha de una regla o en alguna forma sentencial. Por ejemplo:
A -> A B | a | λ
B -> b | a | λ
Gramáticas Formales

● Recursividad:

○ La definición de un concepto utiliza a ese mismo concepto en la

definición.
○ Existen varios niveles de recursividad:
■ Producción recursiva.
■ Gramática recursiva.
■ Recursividad por la izquierda.
■ Recursividad por la derecha.
Gramáticas Formales

● Producción recursiva:

○ Si el mismo símbolo no terminal aparece en los dos lados de la

producción.
○ Es decir, existe un A ∈ ΣN tal que (A -> xAy) ∈ P, (x, y ∈ Σ*)
○ Ejemplos:
■ A -> 0A0
■ B -> B10
■ C -> 111C
Gramáticas Formales

● Gramática recursiva:

○ Si existe al menos una producción recursiva en su conjunto de

producciones.
○ Ejemplo: S -> (S) | ()
Gramáticas Formales

● Recursividad por la izquierda:

○ Si el símbolo no terminal aparece el primero de la parte derecha.

○ Es decir, A -> Ay (A ∈ ΣN , y ∈ Σ*)
○ Ejemplo: B -> B10 es recursiva por la izquierda.
Gramáticas Formales

● Recursividad por la derecha:

○ Si el símbolo no terminal aparece el último en la parte de la derecha.

○ Es decir, A -> xA (A ∈ ΣN , x ∈ Σ*)
○ Ejemplo: C -> 111C es recursiva por la derecha.
Gramáticas Formales

● Factorización a izquierdas:

○ Proceso que elimina el problema de que aparezcan producciones de

un mismo símbolo no terminal en cuya parte derecha, la primera parte
sea común. Ejemplo:

S -> if C then S else S | if C then S | repeat S until C | repeat S forever

○ Algoritmo:
Por cada A ∈ ΣN S -> if C then S A’| repeat S S’
Si A -> βα1 | βα2 A’-> else S | λ
cambiar esas reglas por: S’ -> until C | forever
A -> β A’
A’ -> α1|α2
Gramáticas Formales

● Eficiencia en el diseño de gramáticas:

○ Gramáticas limpia: si no tiene reglas innecesarias y símbolos

inaccesibles.

○ Gramática bien formadas: si está limpia, no tiene reglas generativas y

no tiene reglas de redenominación.
Gramáticas Formales

● Reglas innecesarias:

○ Son las que tienen la forma A -> A (A ∈ ΣN ).

○ Se deben eliminar de las gramáticas, ya que no generan derivaciones
útiles.

CON SIN

S -> aA S -> aA
A -> aA | A | a A -> aA | a
Gramáticas Formales

● Símbolos inaccesibles:

○ Aquellos símbolos no terminales A ∈ ΣN que no pueden ser

alcanzados por derivaciones desde el axioma de la gramática, S. Es
decir, no hay derivaciones S -> xAy.

CON SIN

S -> D0 | E10 | λ S -> D0 | E10 | λ

B -> 1C3 D -> 1S
C -> C E -> 1E
D -> 1S
E -> 1E
 Gramáticas Formales

● Reglas no generativas:

○ Una regla es no generativa cuando A -> λ, A ≠ S.

○ Para eliminarlas, se puede seguir el algoritmo:

P’ = P CON SIN
Repetir
Por cada P = (A -> λ) ∈ P’ ^ (A ≠ S) S -> C0B | λ S -> C0B | 0B|
P’ = P’ – {P}
B -> BC | λ
Por cada P’ = (B -> xAy) ∈ P’ (x, y ∈ Σ*)
C -> 0B | λ C0 | 0 | λ
P’ = P’ U {(B -> xy)} – {P’}
B -> BC | C
Hasta que todas las reglas sean generativas
C -> 0B | 0
Gramáticas Formales

● Reglas de redenominación:

○ Una regla es de redenominación cuando A -> B con A, B ∈ ΣN

○ Para eliminarlas, se borra esa regla y se genera una nueva producción
A -> x por cada B -> x, con x ∈ Σ*.

CON SIN

S -> C0B | 0B|C0 | 0 | λ S -> C0B | 0B|C0 | 0 | λ

B -> BC |C B -> BC |0B | 0
C -> 0B | 0 C -> 0B | 0
Gramáticas Formales
● Formas Normales:

○ Son simplificaciones a las reglas de producción de una gramática de

tipo 2 (independientes de contexto).
○ Proveen una forma canónica en la cual representar una GIC.
○ Su utilización se traduce en compiladores más eficientes para
diversos lenguajes de programación.
○ Tipos:
■ Forma Normal de Chomsky (FNC o CNF)
■ Forma Normal de Greibach (FNG o GNF)
■ Forma Normal de Backus-Naur (FNB o BNF)
Gramáticas Formales
● Forma Normal de Chomsky (FNC o CNF):

○ En esta forma de representar las gramáticas, las producciones pueden

tener las siguientes formas:
P = {(S -> λ) | (A -> BC) | (A -> a) / A, B, C ∈ ΣN, a ∈ ΣT }

G G en FNC

A -> CB2 | 1B| λ A -> CD | EB | λ

B -> BC |1 B -> BC |1
C -> 2 C -> 2
D -> BC
E -> 1
Gramáticas Formales
● Algoritmo para transformar GIC a FNC:

○ Entrada: G = (ΣN, ΣT, S, P)

○ Salida: G’ = (ΣN’, ΣT, S, P’) en FNC

○ Mientras existen producciones cuyo lado derecho no respeta la FNC
hacer:
■ 1) Reemplazar cada producción A -> B / B -> v1| v2|…| vn por la
producción A ->GIC
v1| v2|…| vn FNC

A -> B A -> a | b |c
B -> a | b |c
Gramáticas Formales
● Algoritmo para transformar GIC a FNC:

○ 2) Para cada producción, si su lado derecho tiene dos o más símbolos

y contiene algún terminal v, reemplace las apariciones de v por un
nuevo no terminal V. Agregue la regla V -> v. Es decir, para un no
terminal V / V ∉ ΣN, ΣN’ = ΣN ∪ {V}, P’ = P ∪ {V -> v}

GIC FNC

A -> pBq A -> PBQ

P -> p
Q -> q
Gramáticas Formales
● Algoritmo para transformar GIC a FNC:

○ 3) Para cada producción B -> C1C2...Cn, donde n > 2, reemplazar la

producción por B -> C1D, y D -> C2...Cn, que introducen un nuevo no
terminal D.

GIC FNC

A -> BCDE A -> BC1

C1 -> CDE
Gramáticas Formales
● Algoritmo para transformar GIC a FNC: Ejemplo
GIC FNC
Paso 1:
S -> aSa
S -> b
S -> aSa Paso 2:
S -> T S -> ASA
T -> b S -> b
A -> a
Paso 3:
S -> AB
S -> b
A -> a
B -> SA
Gramáticas Formales
● Forma Normal de Chomsky (FNC o CNF):

○ Ventajas:

■ Todo árbol de derivación es de tipo binario.

■ Toda palabra de longitud n es derivable en 2n-1 pasos.

○ Estos elementos son de importancia teórica y práctica (por ejemplo,

programación de compiladores).
Gramáticas Formales
● Forma Normal de Greibach (FNG o GNF):

○ Es otra forma de representar las gramáticas de tipo 2, las

producciones pueden tener las siguientes formas:

P = {(S -> λ) | (A -> aX) / A ∈ ΣN, X ∈ ΣN*, a ∈ ΣT }

G G en FNC

A -> CB2 | 1B| λ A -> 2BC | 1B | λ

B -> BC |1 B -> 1B’ |1
C -> 2 B’ -> 2B’ | 2
C -> 2
Gramáticas Formales
● Forma Normal de Greibach (FNG o GNF):

○ Sheila Greibach

■ Nacida en New York (1939), obtuvo su doctorado en 1963 en la

Universidad de Harvard.
■ Actualmente trabaja en el Departamento de Ciencias de la
Computación de la UCLA (Universidad de California, EEUU).
Gramáticas Formales
● Algoritmo para transformar GIC a FNG:

○ Entrada: G = (ΣN, ΣT, S, P)

○ Salida: G’ = (ΣN’, ΣT, S, P’) en FNG

○ 1) Eliminar la recursión a izquierda (por ejemplo: A -> Aa) sustituyendo
cada sublenguaje generado recursivamente por un conjunto de reglas
equivalente, pero sin recursión.
○ 2) Agregar nuevas reglas de reescritura y no terminales para llevar las
reglas existentes a la forma de Greibach:
■ a) Reemplazar A ∈ ΣN en cada α -> β, de a una por vez, para
introducir terminales a izquierda.
■ b) Reemplazar cada a ∈ ΣT que no está en la parte izquierda de β
Gramáticas Formales
● Algoritmo para transformar GIC a FNG: Ejemplo

GIC FNG

S -> AB Paso 1: Paso 2a: Paso 2b:

S -> B S -> AB S -> bB S -> bB
A -> Aa S -> B S -> bDB S -> bDB
A -> b A -> b S -> bb S -> bE
B -> Ab A -> bD S -> bDb S -> bDE
S -> c S -> c
B -> c D -> aD D -> aD D -> aD
D -> a D -> a D -> a
B ->Ab B -> bb B -> bE
B -> c B -> bDb B -> bDE
B -> c B ->c
E -> b
Gramáticas Formales
● Forma Normal de Greibach (FNG o GNF):

○ Ventaja:

■ Se conoce que cada palabra de longitud n es derivable en n pasos.

Gramáticas Formales
● Forma Normal de Backus-Naur (FNB o BNF):

○ En 1959 desarrollaron la notación BNF.

○ John Backus nació en 1923, en Philadelphia (EEUU). Inventó el
lenguaje Fortran y el lenguaje funcional FP.
○ Peter Naur fue uno de los diseñadores del lenguaje ALGOL, precursor
de la programación estructurada en alto nivel.
○ BNF fue desarrollada en paralelo con las GIC de Chomsky.
○ La notación BNF es equivalente a usar Diagramas de Conway
(tradicionales en Pascal).
Gramáticas Formales
● Forma Normal de Backus-Naur (FNB o BNF)

○ Conjunto de reglas que definen, con precisión, la sintaxis de los

componentes y de las estructuras de un Lenguaje de Programación.
○ Cada regla BNF se forma con elementos provenientes de 3 conjuntos
disjuntos (convenciones):
■ Metavariables o noterminales, palabras encerradas entre
corchetes angulares (ejemplo: <identificador>, <letra>, <digito>).
■ Terminales, símbolos del alfabeto. Se los llama terminales porque
no existen reglas de producción para ellos.
■ Metasímbolos, caracteres o grupos de caracteres que ayudan a
representar estas reglas (ejemplo: <>, ::=, |).
■ El lado izquierdo debe tener únicamente un no terminal (para
cumplir con la definición de GIC)
Gramáticas Formales
● Forma Normal de Backus-Naur (FNB o BNF):

BNF para validar la correcta apertura y cierre de una palabra de

paréntesis.
Ejemplo: ((()))

<palabra_par> ::= <palabra_par> <parentesis> | <parentesis>

<parentesis> ::= (<palabra_par>) | ()
Gramáticas Formales
● Forma Normal de Backus-Naur (FNB o BNF):

BNF de un identificador en ALGOL

<identificador> ::= <letra> |
<identificador> <letra> |
<identificador> <dígito>
<letra> ::= a | b | c | … | z | A | B | C | … | Z
<dígito> ::= 0 | 1 | 2 | … | 9

BNF de números enteros en ALGOL

<número entero> ::= <entero sin signo> |
+ <entero sin signo> |
- <entero sin signo>
<entero sin signo> ::= <dígito> | <entero sin signo> <dígito>
<dígito> ::= 0 | 1 | 2 | … | 9
Gramáticas Formales
● Otros ejemplos de BNF:
Gramáticas Formales
● Forma Normal de Backus-Naur Extendida (FNBE o EBNF):

EBNF de un identificador en Pascal

<identificador> ::= <letra> { <letra o dígito> }
<letra o dígito> ::= <letra> | <dígito>
<letra> ::= a | b | c | … | z | A | B | C | … | Z
<dígito> ::= 0 | 1 | 2 | … | 9

EBNF de sentencias if y while en ALGOL

<sentencia if> ::= if <expresión> then <sentencia>|
if <expresión> then <sentencia> else <sentencia>

<sentencia while> ::= while <expresión> do <sentencia>

Gramáticas Formales
● BNF que utiliza el MROC (Manual de Referencia Oficial del ANSI C):

○ Los noterminales están escritos en itálica, eliminándose los

metasímbolos < y >.
○ El “operador es” está representado por : (“dos puntos”).
○ No existe el metasímbolo | (“ó”), sino que cada lado derecho de un
determinado noterminal se escribe en una línea separada.
○ En algunos casos se usa el metasímbolo uno de para representar
varios lados derechos que son símbolos para un no terminal.
○ Los terminales se escriben en negritas.
○ Un símbolo opcional está indicado con un subíndice op.
○ El lado derecho de una regla recursiva se representa como el BNF
original.
Gramáticas Formales
● BNF que utiliza el MROC. Ejemplos:

BNF de un identificador en ANSI C

identificador : noDígito
identficador noDígito
identificador dígito
noDígito : uno de _ a b c … z A B C … Z
dígito : uno de 0 1 2 3 4 5 6 7 8 9

BNF para algunos operadores y caracteres de puntuación del ANSI C

operador : uno de ++ * + & ! sizeof / % < <= == != && || ?: = +=

carácterPuntuación : uno de ( ) { } , ;
Gramáticas Formales
● BNF que utiliza el MROC. Ejemplos:

BNF de sentencias de selección en ANSI C

sentSelección : if ( expresión ) sentencia
if ( expresión ) sentencia else sentencia
switch ( expresión ) sentencia

BNF de sentencias de iteración en ANSI C

sentIteración : while ( expresión ) sentencia
do sentencia while ( expresión ) ;
for ( expresiónop ; expresiónop ; expresiónop ) sentencia
Gramáticas Formales
● Otros usos de BNF:

○ Si bien el metalenguaje BNF fue diseñado para describir la sintaxis de

los Lenguajes de Programación, también puede ser aplicado a otras
áreas.
○ Ejemplo: Se necesita describir un listado de los alumnos de una
Universidad en los que consten los siguientes datos: (a) nombre y
apellido; (b) legajo; (c) código de carrera.

BNF de Listado de Alumnos

listado : alumno
listado alumno
alumno : nombreApellido legajo códigoCarrera
nombreApellido : apellido , nombre
...
Ejercicios
● A1. Describa el orden en que se aplican las producciones {S -> aaT, T -> λ,
T -> b} para generar las palabras del Lenguaje Formal L ={aa, aab}. ¿La
producción T -> λ genera la palabra vacía del lenguaje?
● A2. ¿Qué Lenguaje Formal genera la gramática G = <{S,T}, {a,b}, {S -> aT,
T -> a, T -> λ}, S>? Justifique.
● A3. Sea la Gramática Formal con producciones: {S -> aT | bQ, T -> a | b,
Q -> a | λ} ¿La gramática con estas seis producciones genera la palabra
bab? Justifique. ¿Cuál es el Lenguaje Formal generado por esta
gramática? Justifique.
● A4. Escriba las producciones de una GR que genere el Lenguaje Regular L
= {anb / 1 ≤ n ≤ 3}. Escriba la definición formal de la GR desarrollada.
● A5. Escriba las producciones de una GR que genere el Lenguaje Regular L
= {anbn / 0 ≤ n ≤ 2}. Escriba la definición formal de la GR desarrollada.
Ejercicios
● A6. Indique cuál es la mínima palabra del LR generado por la GR {S -> aS|
aT, T -> b}. Muestre cómo la genera.
● A7. Escriba la sucesión de producciones que aplicaría para generar la
palabra aaab del LR definido en el punto anterior.
● A8. Escriba una GR que genere cualquier secuencia de uno o más dígitos
decimales. Escriba una GQR que genere cualquier secuencia de uno o
más dígitos decimales. Compare la cantidad de producciones de ambas
gramáticas.
● A9. Escriba las producciones de una GQR que genere un LR infinito cuyas
palabras son secuencias de tres o más dígitos octales (en base 8).
● A10. Transforme las producciones de la GQR obtenida en el punto anterior
en producciones de una GR equivalente.
● A11. ¿Una GR es siempre una GIC? Justifique. ¿Una GIC es siempre una
GR? Justifique.
● A12. ¿Cuál es la mínima palabra generada por la GIC { S -> aSb | a}?
Justifique. ¿Cuál es la palabra que le sigue en longitud?
Ejercicios
● A13. Describa, por comprensión, el LIC generado por la GIC <{S -> aSb | a}>
● A14. Sea el lenguaje L = {anbn+1 / n ≥ 0}. Escriba las producciones de una
GIC que lo genere.
● A15. Sea el lenguaje L = {a2nbn+1ar / n ≥ 1, r ≥ 0}. Escriba la definición formal
de una GIC que lo genere.
● A16. Demuestre que una GQR es un caso particular de una GIC.
● A17. Comprueba que la GI que genera el lenguaje L = {ai / i es una
potencia positiva de 2}. G = <{S, A, B, C, D, E}, {a}, {S -> ACaB, Ca -> aaC, CB
-> DB, CB -> E, aD -> Da, AD -> AC, aE -> Ea, AE -> λ}, S> puede generar la
palabra aaaa. Indique, paso a paso, cada producción que aplica y explique
por qué utiliza la producción elegida.
● A18. Dada la GIC {S -> aSb|ab}, determine, aplicando una derivación
horizontal, si la cadena aaabbbb es una palabra del LIC generado por esta
GIC. Dibuje la misma derivación, pero en forma de árbol.
Ejercicios
● A19. Sea el LIC infinito L = {anbcnb / n ≥ 1}. Escriba la Definición Formal de
una GIC que genere este Lenguaje Formal.
● A20. Dada la GIC construida en el punto anterior, utilice derivación vertical
a izquierda para determinar si las siguientes cadenas son o no palabras
del LIC generado: aaabcccb, aabbccb, aaabcccbb, aaccb.
● A21. Escriba una GR equivalente a la GQR <{S -> L | SL | SD, L -> a|b|c|d, D -
> 2|3|4|5|6}>. ¿Cuál es más sencilla de ser leída? Justifique su respuesta.
● A22. Dada la GQR <{S -> L | SL | SD, L -> a|b|c|d, D -> 2|3|4|5|6}>. Determine
si las siguientes palabras son válidas: ab23, 2a3b. Verifiquelo aplicando
derivación a izquierda y derivación a derecha.
Ejercicios
● A23. Supongamos un Lenguaje de Programación en el que sus
expresiones aritméticas están formadas por los números enteros 2 y 6, el
operador de suma y siempre termina con un “punto y coma”. Algunas
expresiones aritméticas de este Lenguaje de Programación son: {6;
2+2+6; } Vamos a construir una GIC que genere la totalidad de estas
expresiones aritméticas. Para ello, debemos definir el vocabulario de no
terminales, el vocabulario de terminales, el axioma y el conjunto de
producciones. Supongamos que el vocabulario de no terminales esta
formado por: S (el axioma), E (de expresión) y T (de término). Los
terminales son 2, 6, + y ; (punto y coma). Las producciones de la GIC que
genera el lenguaje de estas expresiones aritméticas son: {S -> E; E -> T | E
+ T T -> 2 | 6}. Determine, aplicando derivación a:
○ A. izquierda, si 6; es una expresión correcta.
○ B. izquierda, si 6+6+6+; es una expresión correcta.
○ C. derecha, si 6+6+6+; es una expresión correcta.
○ D. izquierda, si 6+6+6+2; es una expresión correcta.
Ejercicios
● A24. Dada la siguiente Gramática Formal:
Identificador -> Letra | Identificador Letra | Identificador GuiónBajo Letra
GuiónBajo -> _
Letra -> A | B | C | … | Z

○ A. Construya el árbol de derivación para generar el identificador R_X_A.

○ B. Verifique, mediante derivación, que A__B (hay dos guiones bajos
consecutivos) no es un identificador válido para el lenguaje de
programación.
Ejercicios
● A25. Dada la siguiente Gramática Formal:
Expresión -> Término| Expresión + Término
Término -> Factor | Término * Factor
Factor -> Número | (Expresión)
Número -> 1 | 2 | 3 | 4 | 5

○ A. Construya el árbol de derivación para generar la expresión 1 + 2 * (3

+ 4) + 5.
○ B. ¿Cuál es la menor expresión que se puede derivar desde la GIC?
Escríbala y justifique su respuesta.
○ C. ¿Es ((2)) una expresión válida? Demuestre que sí o que no por
derivación.
○ D. Intente derivar 1 + 2 + + 3.
Ejercicios
● A26. Dada la siguiente Gramática Formal:
E -> E + E | E * E | (E) | N
N -> 1 | 2 | 3 | 4 | 5

○ A. Describa formalmente la GIC.

○ B. Construya el árbol de derivación para generar la expresión 1 + 2 * (3
+ 4) + 5.

● A27. Dada la siguiente Gramática en BNF:

<número entero> ::= <entero sin signo> | + <entero sin signo> | - <entero
sin signo>
<entero sin signo> ::= <dígito> | <entero sin signo> <dígito>
<dígito> ::= 0 |1|2|3|4|5|6|7|8|9

○ A. Derive el número entero -123456.

Resueltos
● A1. S -> aaT, T -> λ => aa
S -> aaT , T -> b => aab
No
● A2. Lenguaje Regular generado con una gramática irrestricta o con
estructura de frase.
● A3. No. L = {aa, ab, ba, b}
● A4. G: <{a, b}, {S, A, B, C}, S, P> donde P:
S -> aA A -> b | aB B -> b | aC C -> b
● A5. G: <{a, b}, {S, A, B, C}, S, P> donde P:
S -> λ | aA A -> b | aB B -> bO C -> b
Resueltos
● A19. G: <{a, b, c}, {S, A}, S, P> donde P:
S -> Ab
A -> aAc | abc

● A20.
Ejercicios
● B1. Obtener las derivaciones de las palabras 002 y 0001 a partir de la
siguiente gramática: G = <{0, 1, 2}, {A, B}, A, {(A::=0B), (A::=2), (B::=0A),
(B::=1)} >. Describir el árbol de derivación y obtener el lenguaje que
genera.
● B2. Dada la siguiente gramática, realizar factorización a izquierda y
eliminación de recursividad por la izquierda. G = <{or, and, not, =, (, ), id},
{C}, C, P>, donde P:
C -> C and C | C or C | not C | (C = C) | id
● B3. Dada la siguiente gramática, que utiliza la notación polaca inversa
(todos los operandos de las operaciones se colocan antes de los
operadores), factorizar a izquierdas y eliminar la recursividad por la
izquierda. G = <{id, num, func, +, *, /, -, (, ), ., ;, <, >, =}, {S, N, M, O, R}, S, P>,
donde P:
S -> S;S | S. |(NNR) | (idN=)
N -> MNON | MNO | id | num
M -> N | func(N) | func(M)
O -> + | * | - | /
R -> < | > | ==
Ejercicios
● B4. Dada la gramática G = <ΣT, ΣN, E, P>, donde ΣT = {a, +, *, ), (}, ΣN = {E, T,
F}, E es el axioma y P es:
E -> E + T | (E) | a
T -> T * F | (E) | a
F -> (E) | a
Eliminar la recursividad por la izquierda y construir el árbol de derivación
para las sentencias: a+a+a+a+a y a+(a+a).
● B5. Con el alfabeto Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} encontrar una gramática
regular que genere números múltiplos de 3 de cualquier número de cifras.
● B6. Obtener el lenguaje que genera la siguiente gramática regular G = <Σ T,
ΣN, E, P>, donde ΣT = {0, 1}, ΣN = {S}, S es el axioma y P es:
S -> 0S | 1S | λ

● B7. Definir una gramática regular que dado el alfabeto ΣT = {a, b, c, d},
genere cadenas que no contengan la secuencia “bc”.
Ejercicios
● C1. Dé una gramática que genere cada uno de los siguientes lenguajes. En
cada caso, defina el conjunto de reglas de producción sin utilizar el
algoritmo de pasaje del autómata finito que reconoce el lenguaje de la
gramática
○ A. L = {w / w ∈ {0, 1}* y w contiene al menos tres ceros} (lineal a la
derecha)
○ B. L = {a2nbij(cc)kan+1 / i, n, k ≥ 0; j > k}
○ C. L = {w / w ∈ {a, b, c}*, la cantidad de a es impar en w, y no se puede
dar la subcadena bc}
○ D. L = {w / w ∈ {a, b, c, d}* y w no contiene addc, d debe ser par, b
impar}
Ejercicios
● C2. Dé una gramática que genere cada uno de los siguientes lenguajes.
○ A. L = {(ab)nc(ba)2m+1 / n ≥ 1; m ≥ 0}
○ B. L = {x / x ∈ {a, b, c}* y x contiene al menos dos b y x contiene la
subcadena bc}
○ C. L = {x / x ∈ {a, b, c}* y x empieza y termina con distinta letra}
○ D. L = {x / x ∈ {a, e, i, f, t, h, n, l, s, w, d}* y x es alguna de las siguientes
palabras reservadas de Pascal: {if, then, else, while, end}}
Ejercicios
● C3. Dado el AFD, indique para cada una de las siguientes gramáticas:
○ A. Si es regular.
○ B. Si genera el mismo lenguaje que reconoce el AFD. En los casos en
que esto no ocurra, justifique por qué.
Ejercicios
G1 G2 G3 G4
S -> λ S -> λ S -> λ S -> λ
S -> aA S -> a S -> a S -> A
S -> bB S -> aA S -> aS A -> a
S -> cC S -> bB S -> bB A -> aA
A -> aA S -> cC S -> cC A -> bB
A -> bB A -> a B -> aB A -> cC
A -> cC A -> aA B -> bA B -> aB
B -> aB A -> bB B -> b B -> bA
B -> bA A -> cC C -> cD B -> b
C -> cD B -> aB D -> cE C -> cD
D -> cE B -> bA D -> c D -> cE
E -> cC B -> b E -> cC D -> c
C -> cD E -> cC
D -> cE
D -> c
E -> cC
Ejercicios

● C4. Para cada una de las siguientes gramáticas determine el lenguaje que
genera.

G1 G2 G3 G4
S -> 1B S -> aA S -> aA S -> aA
S -> 1 A -> bB A -> bB A -> aB
A -> 1B B -> aA B -> bB B -> aA
A -> 1 B -> aC B -> c B -> b
B -> 0A C -> aD B -> cC B -> bC
C -> a C -> cC C -> bC
D -> aD C -> c C -> b
D -> a
Ejercicios

● C5. Defina una GIC para cada uno de los siguientes lenguajes:
Ejercicios
● C6. Determine el lenguaje generado por cada una de las siguientes
gramáticas:

G1 G2
S -> λ S -> xAyC
S -> AB S -> xByyC
S -> A S -> xyC
S -> B S -> xyyC
A -> aAb A -> xAy
A -> ab A -> xy
B -> bB B -> xByy
B -> b B -> xyy
C -> zC
C -> z
Ejercicios

● C7. Suponer los siguientes lenguajes, diseñe las gramáticas

correspondientes:
○ A. L = {a2ibi+j(cc)kan+1 / i, n, k ≥ 0; j > k}
○ B. L = {a2idndi+jbn+1 / i, n, j ≥ 0} U {aj+1dndj+kbn+1 / k, n, j ≥ 0}
○ C. L ={dn cj (ab)2s et+2n / s, t, n ≥ 0 y j > t} U {d2k(ab)2h+1 ek+i / h, k ≥ 0; i > k}
Ejercicios
● C8. Diseñar las gramáticas correspondientes para los siguientes
lenguajes:
○ A. L = {w / w ∈ {a, b}*}
○ B. L = {a2nbij(cc)kan+1 / i, n, k ≥ 0; j > k}
○ B. L = {a2idndi+jbn+1 / i, n, j ≥ 0} U {aj+1dndj+kbn+1 / k, n, j ≥ 0}
○ C. L ={dn cj (ab)2s et+2n / s, t, n ≥ 0 y j > t} U {d2k(ab)2h+1 ek+i / h, k ≥ 0; i > k}
Ejercicios
● C9. Dado los siguientes lenguajes diseñar la gramática correspondiente
según su tipo:
○ A. L está dado por la ER: (a|bc)* (dd|c)*
○ B. L = {an bj (hf)h ek et+2h/ t, n ≥ 0; h ≥ 1; k > n; j > t}
○ C. L = { e2n dt (bd)s f2k+n / t, n ≥ 0, s > 0 y k > t } U {(ee)k+1 hi+1 d2t / k, i ≥ 0 ;
t > k}
○ D. L = { e2n dt (bd)s f2k+n / t, n ≥ 0, s > n y k > t }
○ E. L = {w / w ∈ {a, b, c}* donde el símbolo “a” aparece de a pares (aa),
el símbolo c puede venir luego de una b u otra c}
Ejercicios
● C10. Diseñar BNF para Asignaciones de operaciones aritméticas o
booleanas:
○ Las asignaciones se representan con el símbolo :=
○ Las variables pueden ser alfanuméricas, no pudiendo comenzar con
un número. Ejemplo: VALOR1 -> válido 1VALOR ->inválido
○ Las operaciones aritméticas son: suma (+), resta (-), división (/),
multiplicación (*) y potencia (^).
○ Las operaciones lógicas son AND, OR, NOT
○ Se podrán tener operaciones entre ()
○ Ejemplos de asignaciones: VAR12 := (VAR1 + VAR2) * VAR3 ^ VAR4 /
VAR5 Otro Ejemplo: VARBOL2 := VAR1 AND VAR3 NOT VAR5 AND
(VAR6 OR VAR7)
Ejercicios
● C11. Dado el siguiente BNF para expresiones lógicas
<exp_lógica> ::= <exp_lógica> or <exp_lógica> |
<exp_lógica> and <exp_lógica> |
(<exp_lógica>) | not <exp_lógica> |
true | false | <var_lógica>
<var_lógica> ::= A | B | C | … | Z
● A. Determine usando árboles de derivación, si las siguientes son
expresiones lógicas.
○ i. A or ((B and not (B or A)) and true
○ ii. ((A and B) or C) and not A or B
○ iii. A and (C or B) or not (true and false)
Ejercicios
● C11.
○ B. Determine si el BNF dado es o no ambiguo. Justifique. En caso de
ser ambiguo, defina si es posible un BNF no ambiguo que genere el
mismo lenguaje.
● C12. Dado los siguientes lenguajes determinar de qué tipo son y diseñar la
gramática del tipo correspondiente:
Resueltos
● C2. C) L = {x / x ∈ {a, b, c}* y x empieza y termina con distinta letra}
S -> aA | bB | cC
A -> aA | bA | cA | b | c
B -> aB | bB | cB | a | c
C -> aC | bC | cC | a | b
Ejercicios
● O1. Diseñar las gramáticas más restrictivas correspondientes para los
siguientes lenguajes:
○ A. L = {w / w ∈ {a, b}*}
○ B. L = {w / w ∈ {a, b, c}* , la cantidad de a es impar en w, y no se
puede dar la subpalabra bc}
● O2. Dada la siguiente gramática de tipo 2: {S -> λ; S -> AaB; S -> BbA; A ->
a; A -> aAa, A -> bAa; B -> b; B -> bBb; B -> aBb}
○ A. Cadena más corta.
○ B. Varias cadenas del lenguaje.
● O3. Dada la siguiente gramática de tipo 2: {S -> [A]; A -> a; A -> aaA}
○ A. Cadena más corta.
○ B. Varias cadenas del lenguaje.
Ejercicios
● O4. Obtenga la gramática G tal que L(G) = {ww-1 / w,w-1 ∈ Σ*} Σ = {a,b}
● O5. Dado el alfabeto Ʃ = {a, b, c, d} y el lenguaje L = {a 2k b2n ck dj / k, n, j ≥
0 }. Definir formalmente una GIC que lo genere.
● O6. Dada la siguiente gramática ambigua, G=({S,B}, {0,1}, S, P), donde P
son las producciones, P = {(S -> 0BB), (B -> 1S), (B -> 0S), (B -> 0)}. Mostrar
los diferentes árboles de derivación para la cadena 010000000.
● O7. Dada la siguiente gramática ambigua, G=({E}, {+, *, cte}, E, P), donde
P son las producciones, P = {(E -> E + E), (E -> E * E), (E -> cte)}. Derivar la
cadena: cte + cte * cte, mostrando los diferentes árboles de derivación.
Ejercicios
● O8. Diseñar una gramática en formato BNF para:
○ A. Códigos postales en formato antiguo (Por ej. 1234, 8366, pero no
422 o 0027)
○ B. Comentarios acotados por /* y */ Ʃ = {letras, *, /}
○ C. Patentes de autos formato anterior al actual.
○ D. Fecha con formato dd/mm/yyyy.
● O9. Diseñar una gramática en formato BNF para:
○ A. Describir los números naturales (considerar N u {0})
○ B. Idem anterior sin ceros a la izquierda.
○ C. Probar si las gramáticas generan las cadenas 408 y 0015.
Ejercicios
● O10. Diseñar una GIC en notación BNF para las expresiones aritméticas, y
luego utilizarla para definir la GIC de la asignación en lenguaje C.
Considerar cte, id y los símbolos de suma, resta, multiplicación y división
como elementos terminales.
● O11. Diseñar una GIC en notación BNF en la que se puedan generar
cadenas de este tipo: if <condición> then <acción> else <acción>
(opcional) endif, donde acción, es de la forma: id = cte u otra sentencia
if. Condición, es de la forma: id operador cte, y operador, es un
operador lógico: >, <, <>. Elementos terminales: if, then, else, endif, id, cte,
=, >, <, <>. 
○ Ejemplo de cadena válida: if id > cte then id = cte else id = cte endif.
Probar si acepta una cadena con if anidado.
Ejercicios
● O12. Definir una GIC que genere declaraciones simples de métodos en el
lenguaje de programación Java: 
○ tipo_de_retorno nombre_del_metodo ( lista de parámetros ) Donde:
■ lista de parámetros será una enumeración de cero o más
parámetros, separados por comas. Los parámetros tendrán la
forma:
● tipo nombre
■ nombre y nombre_del_metodo: será una sucesión de letras y
dígitos que comienza con una letra.
■ tipo_de_retorno y tipo: Considerarlos como terminales.
Resueltos
● O5. L = {a2k b2n ck dj / k, n, j ≥ 0 }
G: <{a, b, c, d}, {S, D, B, A}, S, P> donde P:
S -> λ | D | BD | A | AD
D -> dD | d
B -> bbB | bb
A -> aaAc | B | aac