Jerarquia de Chomsky

Teoría de la Computabilidad – Curso Dr. C. Chesñevar– Primer Cuatrimestre de 2012

Relación entre Modelos Estudiados

Teoría de la
Computabilidad

Gramáticas
Est.Frases

Autómatas
a Pila

Módulo 18:
Teoremas de Equivalencia
Gramáticas Estructuradas por frases –
Máquinas de Turing

Autómatas
Finitos

Máquinas
de Turing

?

Funciones
Recursivas
Parciales

PrimerCuatrimestre de 2012

?

¿Qué relación
existe entre
MT y GEF?

Redes
de Petri

equivalentes en poder
computacional

Departamento de Cs. e Ing. de la Computación
Universidad Nacional del Sur
Bahía Blanca, Argentina
1

Lema sobre Jerarquía de Chomsky

2

Lema sobre Jerarquía de Chomsky

Lema: Sean CLR, CLLC y CLSC las clases de
lenguajes regulares, libres de contexto y
sensiblesal contexto. Ent. CLR ⊂ CLLC ⊂ CLSC .

Pero... ¿las restricciones no agregadas sobre
el tipo j < i dan alguna ventaja?
Sí, pues hemos
evidencian:

En otras palabras: C3 ⊂C2 ⊂ C1 , donde Ci
denota la clase de lenguajes de tipo i

visto

ejemplos

que

lo

Sea L={anbn|n>=0}. Ent. L∈C2 pero L ∉ C3
∈

Demostración:

Sea L={anbncn|n>=0}. Ent. L∈C1 pero L ∉ C2
∈

Notemos quepor def. en la Jerarquía de
Chomsky, si una gramática es de tipo i
constituye una restricción sobre el tipo j si i>j.

Luego se verifica que C3 ⊂ C2 ⊂ C1, como
queríamos demostrar.

Esto permite asegurar que si G es de tipo i,
ent. no puede generar una cadena que no
puede generar una G’ de tipo j. Luego Ci ⊆ Cj
3

4

Repensando a MT según Chomsky

Configuraciones de MT como cadenasUna MT puede pensarse como una serie de cadenas
resultantes de aplicar las distintas reglas de
transición...

Sea T=(S, Σ , δ s0 ,F) una MT, con
δ,
S={ s0, s1, s2, s3, s4, s5, s6, sf },
Σ = { ◊, x, y, Ψ } y
F = { sf },
y las reglas de transición:

Intuición:
....

◊

x

x

y

x

◊

....

[◊ x x y x ◊] ó
[◊ ◊ ◊ x x y x ◊]

Más formalmente:
....

◊

x

x

ysi

x

◊

....

[◊ x si x y x ◊]
Símbolo actual inmed. a
derecha de si

5

δ(s0 , ◊) = (s1 , R)
δ(s1 , x) = (s1 , R)
δ(s1 , y) = (s2 , R)
δ(s2 , y) = (s2 , R)
δ(s2 , ◊) = (s3 , L)
δ(s3 ,x) = (s4 , ◊)
δ(s3 , y) = (s4 , ◊)

δ(s3 , ◊) = (s5 , R)
δ(s4 , ◊) = (s3 , L)
δ(s5 , ◊) = (s6 , Ψ)
δ(s6 , Ψ) = (sf , L)

Nota:
usamos
notación de
4-uplas.

Ψ = símboliza cadenaaceptada
Esta MT reconoce cadenas de
L={xmyn| m ≥ n≥1}
≥0, ≥
6

El uso total o parcial de este material está permitido siempre que se haga mención explícita de su fuente: “Teoría de la Computabilidad –
Transparencias de Clase”. © Dr. Chesñevar, Mg. Cobo, Mg. Martínez, Universidad Nacional del Sur 2002-2010

Teoría de la Computabilidad – Curso Dr. C. Chesñevar– Primer Cuatrimestre de 2012Secuencia de configuraciones
Consideremos el
reconocimiento
de la cadena xxy.
L={xmyn|m≥0,n≥1}
≥ ≥
Si partiendo de la
cadena
[s0 ◊ w ◊]
se obtiene la cadena
[sf ◊ Ψ◊ ]
entonces w es
aceptada por la MT.

[s0 ◊ x x y ◊]
[◊ s1 x x y ◊]
[◊ x s1 x y ◊]
[◊ x x s1 y ◊]
[◊ x x y s2 ◊]
[◊ x x s3 y ◊]
[◊ x x s4 ◊ ◊]
[◊ x s3 x ◊ ◊]
[◊ x s4 ◊ ◊ ◊]

Lema: MT ⇒ GEF (1)
Lema: Sea L unlenguaje aceptado por una
MT. Entonces L es un lenguaje asociado a
una gramática estructurada por frases.

[◊ s3 x ◊ ◊ ◊]
[◊ s4 ◊ ◊ ◊ ◊]
[s3 ◊ ◊ ◊ ◊ ◊]
[◊ s5 ◊ ◊ ◊ ◊]
[◊ s6Ψ ◊ ◊ ◊]
[sf ◊ Ψ ◊ ◊ ◊]

Demostración:
Queremos mostrar que para todo lenguaje
L aceptado por una MT M existe una
gramática G que genera L.
Sea M=(S, Σ, δ s0 ,{sf}) que acepta
δ,
cadenas deteniéndose con sucinta
configurada como ◊Ψ◊, y sea L=L(M).
Ψ
Puede definirse una gramática G que hace
una mímica del comportamiento de M:
7

Lema: MT --> GEF (2)

8

Lema: MT --> GEF (2)

Sea G=(Vn,Vt,I,P), con

P={ I → [sf ◊Ψ◊],
Ψ
◊ ] → ◊◊ ],
By → Ax para c/trans. δ(A,x)=(B,y)
xB → Ax para c/trans. δ(A,x)=(B,R)
Byx → yAx para c/trans. δ(A,x)=(B,L)
[s0 ◊ → λ
λ,
◊ ◊ ] → ◊ ],
◊]→ λ}

Vn = S...