chomsky

1

Curso B´asico de Computaci´on

9 La Jerarqu´ıa de Chomsky
De las tres principales clases de lenguajes que se han estudiado -los conjuntos regulares, los lenguajes libres de contexto, y los lenguajes recursivamente
enumerables- u
´ nicamente los LLC son los que se han caracterizado gramaticalmente. En este cap´ıtulo, se dar´an definiciones gramaticales de los conjuntos
regulares y los lenguajesr.e.
Tambi´en, se introducir´a una nueva clase de lenguajes, que viven entre los
LLC y los lenguajes r.e., proporcionando ambas caracterizaciones m´aquina y
gramatical para esta nueva clase.
Las cuatro clases de lenguajes son a menudo llamadas la jerarqu´ıa de Chomsky,
en honor a Noam Chomsky, qui´en defini´o estas clases como modelos potenciales de lenguajes naturales.

9.1 Gram´
aticasRegulares
Si todas las producciones de una GLC son de la forma A → wB o A → w,
donde A y B son variables y w es una cadena de terminales (posiblemente
vac´ıa), entonces se dice que la gram´atica es lineal derecha. Si todas las producciones son de la forma A → Bw o A → w, entonces la gram´atica se llama
lineal izquierda. Una gram´atica lineal derecha o izquierda se conoce como
gram´
atica regular.
Ejemplo9.1 El lenguaje 0(10)∗ puede ser generado por la gram´atica lineal
derecha
S → 0A
A → 10A|
y por la gram´atica lineal izquierda
S → S10|0

Equivalencia entre gram´
aticas
regulares y aut´
omatas finitos
Las gram´aticas regulares caracterizan a los conjuntos regulares, en el sentido
de que un lenguaje es regular si y s´olo si tiene una gram´atica lineal izquierda
y si y s´olo si tiene unagram´atica lineal derecha. Estos resultados se prueban
en los dos teoremas siguientes.
Teorema 9.1 Si L tiene una gram´atica regular, entonces L es un conjunto
regular.

Feli´
u Sagols Troncoso

Matem´aticas-Cinvestav

2

Demostraci´
on Primero, sup´ongase que L = L(G) para alguna gram´atica
lineal derecha G = (V, T, P, S). Se construye un AFND con movimientos ,
M = (Q, T, δ, [S], {[ ]}) que simulederivaciones en G.
Q consiste de los s´ımbolos [α] tales que α es S o un sufijo (no necesariamente propio) del lado derecho de alguna producci´on en P .
Def´ınase δ por:
1. Si A es una variable, entonces δ([A], ) = {[α]|A → α es una producci´on}.
2. Si a est´a en T y α est´a en T ∗ ∪ T ∗ V , entonces δ([aα], a) = {[α]}.
Entonces una sencilla inducci´on sobre la longitud de una derivaci´on o sucesi´on
∗de movimientos muestra que δ([S], w) contiene [α] si y s´olo si S ⇒ xA ⇒ xyα,
donde A → yα es una producci´on y xy = w, o si α = S y w = . Como [ ] es
∗
el estado final u
´ nico, M acepta w si y s´olo si S ⇒ xA ⇒ w. Pero como cada
derivaci´on de una cadena terminal tiene por lo menos un paso, se puede ver
que M acepta w si y s´olo si G genera a w. Por lo tanto, cada gram´atica lineal
derecha generaun conjunto regular.
Ahora, sea G = (V, T, P, S) una gram´atica lineal izquierda. Consid´erese
G = (V, T, P , S) donde P contiene las producciones de G con lados derechos invertidos, esto es,
P = {A → α|A → αR est´a en P }.
Si se invierten las producciones de una gram´atica lineal izquierda se obtiene
una gram´atica lineal derecha, y viceversa. As´ı, G es una gram´atica lineal
derecha, y esf´acil mostrar que L(G ) = L(G)R . Por lo anterior, L(G ) es un
conjunto regular.
Pero como los conjuntos regulares son cerrados bajo inversi´on, entonces L(G )R =
L(G) es tambi´en un conjunto regular. Luego, cada gram´atica lineal derecha o
izquierda define un conjunto regular.
Ejemplo 9.2 El AFND construido por el Teorema 9.1 a partir de la primera
gram´atica del Ejemplo 9.1 se muestra en la siguientefigura:
Start

[S]

ε

[0A]

0

[A]

ε

[ε]

ε
1
[10A]

Ahora consid´erese la segunda gram´atica del Ejemplo 9.1. Si se invierten sus
producciones, se obtiene

3

Curso B´asico de Computaci´on

S → 01S|0
La construcci´on en el Teorema 9.1 para esta gram´atica produce el AFND de
la siguiente figura:
1
Start

ε

[S]

0

[01S]

[1S]

ε
0

[0]

[ε]

Si se invierten las aristas de dicho AFND e...