Tema4

Asignatura: Teoría de la Computación
Tema 4: Gramáticas independientes del
contexto

Gramáticas Independientes del Contexto (GIC)
Definiciones y propiedades
¿Qué es una gramática?
•
Modelo de estructuras recursivas.
•
Definición de reglas para representar las expresiones de los lenguajes.
•
Especificación rigurosa y explicita de estructura de un lenguaje.
Características:
•
Ausencia deambigüedad, por tanto bien definidas.
•
Rigurosas (claridad, explicitud).
•
Facilitan evaluación: comprobar, conclusiones, derivar.
•
Hacer predicciones: generalización.
•
Desarrollo de aplicaciones.
Existen varios tipos de Gramáticas, las que mas se usan en computación son las gramáticas
generativas, definidas por Noam Chomsky.
Las Gramáticas Generativas constan de la siguiente tupla de elementos:
G = (V,T, P, S)
Donde:
V: conjunto finito de Variables (símbolos no terminales/categorías sintácticas)
T: conjunto finito de símbolos Terminales (alfabeto terminal o alfabeto de símbolos)
P: conjunto finito de Producciones o Reglas (definición recursiva del lenguaje)
Cada regla o producción consta de:
• Cabeza: variable.
• a : símbolo de producción.
• Cuerpo: cadena de 0 o mas símbolos terminales y/ovariables.
Es decir una regla tiene la forma: Cabeza a Cuerpo, por ejemplo: Por ejemplo:
A a aBA donde A,B en V, a en T
S: símbolo inicial
Nota: Se asume que de V I T= 

Prof. Hilda Contreras – Teoría de la Computación (Pregrado)

1

Las gramáticas generativas son modelos matemáticos finitos que nos permiten generar las
cadenas o palabras de un lenguaje finito o infinito.
Según la Jerarquía deChomsky: las gramáticas generativas se clasifican en 4 tipos. Esta
clasificación es inclusiva, es decir tipo 3 ⊂ tipo 2 ⊂ tipo 1 ⊂ tipo 0
Tipo

0

1

2

3

Gramática

Restricciones a la forma
de las Reglas
Irrestricta
Ninguna restricción
µ1µ2 a β1β2 β3
donde µiβi en (V U T)*
La
parte
derecha
Dependientes
del Contexto o contiene como mínimo
Sensibles
de los símbolos de la parte
izquierda
Contexto
AµB aAβB
Donde A,B en V y µ,β en
(V U T)*
Independiente La parte izquierda solo
del Contexto
puede tener un símbolo
A a β,
Donde A en V, y β en (V
U T)*
Regulares
La regla solo puede
tener 2 formas:
A a aB y A a a, donde
A,B en V y a en T

Lenguaje

Autómata

Enumerables
recursivamente

Máquina de
Turing

Dependiente
del Contexto

Autómata
lineales
infinitos

Independiente
del Contexto

Autómata
dePilas

Regulares

Autómata
finito

Gramáticas Regulares (GR)
Son equivalen a los AF pues tratan sobre el mismo tipo de lenguajes: los lenguajes regulares.
Las reglas de las GR tienen en la cabeza solo un variable y en su cuerpo o un símbolo
Terminal o un símbolo Terminal seguido de una Variable, por tanto son de la forma:
A a aB y A a a,
donde A,B en V y a en T
A partir de un AF que reconoce unlenguaje regular se puede obtener una GR que lo
genere. Por ejemplo para el L = (0 + 1)*10, el siguiente AFND lo reconoce:
0,1
inicio

1

q0

q1

0

f1

El AFD equivalente sería:
Prof. Hilda Contreras – Teoría de la Computación (Pregrado)

2

1

0
inicio

1

B

A

0
1

C

0

Para obtener la GR a partir del anterior AFD se debe hacer las siguientes equivalencias:
•
•
•

•

V = Q = { q0, q1, f1 } quepor conveniencia se etiquetaron como { A, B, C }
T = Σ = { 0, 1 }
P, el conjunto de producciones se obtiene aplicando la siguiente transformación: Para
cada transición del AFD de la forma δ(q,a) = p, tal que q,p en Q y a en Σ, se escribe la
regla q Æ ap, y si p en F entonces se agrega la producción q Æ a, es decir como si p
fuese ε.
S = A = q0, es decir el símbolo inicial de la gramática es elestado inicial del AFD

Se esta forma se obtiene que G = ({ A, B, C },{ 0, 1 }, P, A), donde P es el siguiente conjunto de
producciones:
1.
2.
3.
4.
5.
6.
7.

A Æ 1B
A Æ 0A
B Æ 1B
B Æ 0C
BÆ0
C Æ 1B
C Æ 0A

Este conjunto de producciones son de la forma de una Gramática Regular. A partir de A,
símbolo inicial, se sustituyen sucesivamente para generar una cadena formada solo por
símbolos terminales que...