MATEMATICAS

V´
ıctor J. D´
ıaz Madrigal y Jos´ Miguel Ca˜ ete
e
n

Jerarqu´ de Chomsky
ıa
1.

Clasificaci´n de gram´ticas
o
a

2.

Clasificaci´n de lenguajes
o

3.

Gram´ticas regulares
a

4.

Gram´ticas independientes del contexto
a

5.

Gram´ticas dependientes del contexto
a

6.

Gram´ticas sin restricciones
a

LFA, Curso 2004/2005

V´
ıctor J. D´
ıaz Madrigal yJos´ Miguel Ca˜ ete
e
n

Clasificaci´n de gram´ticas
o
a
Chomsky generaliza el concepto de gram´tica G = (VT , VN , S, P ) y propone una clasifia
caci´n (jerarqu´ seg´n la forma que deben tener sus producciones:
o
ıa)
u
Por la izquierda:
Por la derecha:

Regulares (GREG)

A → Aa A → a
A → aA A → a

Independientes del contexto (GIC)

A→v

Dependientes del contexto (GDC)

αAβ →v con |αAβ | ≤ |v |

Con estructura de frase (GEF)

αAβ → γ

donde A, B ∈ VN , a ∈ VT , α, β, γ ∈ V ∗ y v ∈ V +
Para cubrir el caso de la generaci´n de λ en todos los tipos de gram´ticas, se admite la
o
a
inclusi´n de la regla S → λ en GREGs, GICs y GDCs.
o
Se verifica:
El conjunto de las gram´ticas GRs est´ estrictamente contenido en el de las GICs.
a
a
El conjunto de lasgram´ticas GICs est´ estrictamente contenido en el de las GDCs.
a
a
El conjunto de las gram´ticas GDCs est´ estrictamente contenido en el de las GEFs.
a
a

LFA, Curso 2004/2005

V´
ıctor J. D´
ıaz Madrigal y Jos´ Miguel Ca˜ ete
e
n

Clasificaci´n de lenguajes
o
La jerarqu´ de Chomsky implica a su vez una jerarqu´ de lenguajes.
ıa
ıa
Las gram´ticas GREGs por la derecha o izquierdageneran la misma clase de lenguaa
jes LREG denominados regulares. Esta clase coincide con la de los lenguajes aceptados por los aut´matas finitos y la de los lenguajes descritos mediante expresiones
o
regulares.
Las GICs generan la clase LIC de los lenguajes independientes del contexto.
Esta clase coincide con la de los lenguajes aceptados por los aut´matas de pila.
o
Las GDCs generan la clase LDCde los lenguajes dependientes del contexto.
Las GEFs generan la clase LEF de los lenguajes con estructura de frases. Esta
clase de lenguajes coincide con la de los lenguajes aceptados por las m´quinas de
a
Turing.
Se verifica LREG ⊂ LIC ⊂ LDC ⊂ LEF

LFA, Curso 2004/2005

V´
ıctor J. D´
ıaz Madrigal y Jos´ Miguel Ca˜ ete
e
n

Gram´ticas regulares
a
Ejemplo: Las dos gram´ticas Gr yGl generan el lenguaje regular 11∗ 00∗
a
Regular por la derecha

 S → 1A


Gr =
A → 1A | 0B | 0



B → 0B | 0

Regular por la izquierda

 S → C0


Gl =
C → C 0 | D1 | 1



D → D1 | 1

LFA, Curso 2004/2005

V´
ıctor J. D´
ıaz Madrigal y Jos´ Miguel Ca˜ ete
e
n

Gram´ticas independientes del contexto
a
Ejemplo: Las dos gram´ticas G1 y G2 generan ellenguaje independiente del contexto
a
0n 1n 2m con n, m ≥ 0.
Lenguaje
GIC en formato no estricto

 S → AB


G1 =
A → 0A1 | λ



B → 2B | λ

GIC en formato estricto

 S → AB | A | B | λ


G2 =
A → 0A1 | 01



B → 2B | 2

Podemos observar que la gram´tica G1 no es una GIC en sentido estricito ( incluye reglas
a
nulas asociadas a s´
ımbolos que no son elaxioma). Admitiremos, sin embargo, que es una
GIC debido al siguiente teorema.
Teorema Si todas las reglas de una gram´tica G son de la forma A → γ con A ∈ VN y
a
γ ∈ V ∗ , entonces podemos obtener otra gram´tica GIC equivalente a G.
a

LFA, Curso 2004/2005

V´
ıctor J. D´
ıaz Madrigal y Jos´ Miguel Ca˜ ete
e
n

Gram´ticas dependientes del contexto
a
Ejemplo: Sea la GDC G = ({a,b, c}, {S, M }, S, P ) donde

 S → aM c | aSM c




 aM → ab
P=
 bM → bb




 cM → M c
La gram´tica G genera el lenguaje dependiente del contexto an bn cn con n > 0. Un
a
ejemplo de derivaci´n ser´
o
ıa:
S ⇒ aSM c ⇒ aaM cM c ⇒ aabcM c ⇒ aabM cc ⇒ aabbcc
Teorema Toda gram´tica GDC G pueden ser convertida en otra gram´tica equivalente
a
a
G donde todas las...