Revisando la jerarquía de chomsky
-
Upload
ivan-vladimir-meza-ruiz -
Category
Education
-
view
42 -
download
3
Transcript of Revisando la jerarquía de chomsky
Revisando la jerarquía deChomsky
Hierarchies are celestial. In hell all are equal—Nicolás Gómez Dávila
Ivan Meza
Son una tupla , donde:
Gramáticas dependientes decontexto (sensitivas)
G = (V , Σ, P , S) es otro alfabeto que denominamos símbolos no terminales
(generalmente en mayúsculas) es un alfabeto que denominamos símbolos terminales es conjunto de reglas con la forma donde
y que denominamos símbolo inicial
V
ΣP αAβ → αγβα, β ∈ (Σ ∪ V )∗ γ ∈ (Σ ∪ V )+ A ∈ VS ∈ V
W
B
b
S
S
c
B
W
X
B
B
X
→→→→→→→
W
B
b
abc
aSBc
W
X
B
c
b
B
X
¿Alguien ve el error?
W
B
b
b
c
S
S
C
B
W
X
B
C
c
B
X
→→→→→→→→→
W
B
b
b
c
abC
aSBC
W
X
B
C
b
c
c
B
X
Jerarquía de ChomskyLenguaje Gramática Máquina Ejemplo
Dependiente delcontexto
Tipo 1 ( )
??
Independiente delcontexto
Tipo 2 ( )
Autómatade pila
Regular Tipo 3 ( )
Autómatafinito
αV β → αγβww, anbncn
V → αw ,wr anbn
V → aA|ϵw, a∗
El lenguaje aceptado por unaGDCL(G) = {w ∈ |S w}Σ∗ ⇒+
Gramáticas monotónicasSon una tupla , donde:G = (V , Σ, P , S)
es otro alfabeto que denominamos símbolos no terminales(generalmente en mayúsculas)
es un alfabeto que denominamos símbolos terminales es conjunto de reglas con la forma donde y
y que denominamos símbolo inicial
V
ΣP α → β |α| ≤ |β|, αβ ∈ (Σ ∪ V )∗ S → ϵS ∈ V
S
S
cB
bB
→→→→
aSBc
abc
Bc
bc
Las gramáticas dependientes delcontexto (GDC) son equivalenteas las gramáticas monotónicas(GM)
Formas normalesForma normal de Chomsky para GLC
A → BC
A → a
A → ϵ
PropiedadesForma normal de Chomsky
Todas las producciones tienen para Se puede buscar por fuerza brutaToda gramática libre de contexto se reduce a FNC
2n − 1 |w| = n
Reducción: paso ceroAgregar inicial
Agregar → SS0
Reducción: paso unoQuitar transiciones ϵ
Identificar las reglas que producen Crear versiones de otras reglas donde la producción aparece
si y , entonces
Borrar transiciones
ϵ
P → AxB A → ϵ B → ϵ P → Ax|xB|x
ϵ
Reducción: paso dosQuitar transiciones unitarias
Identificar las reglas de la forma (unitarias)Por cada producción agregar Borrar transiciones unitarias
A → BB → α A → α
Reducción: paso tresReducir transiciones largas
Identificar las reglas de la forma Agregar las versiones , ...
Quitar versión original
A → . . .X1 Xn
A → X1A1 →A2 X2A2→An−1 Xn−1Xn
Reducción: paso cuatroRemover terminales
Identificar las reglas de la forma Agregar la regla Y agregar la regla Quitar versión original
A → . . . a. . .X1 Xn
A → . . . . . .X1 Na Xn
→ aNa
Reducir
S → ASA|aBA → B|SB → b|ϵ
Forma normal de Greibach (GLC)
A → a . . .A1 An
S → ϵ
Forma normal de Kuruda (GDC)
AB → CD
A → BC
A → B
A → a
En resumen
GLC tienen FNC y FNGGM tienen FNKToda GLC se puede transformar a FNC y FNG; son debilmenteequivalentesToda GM se puede transformar a FNK; son debilmente equivalentes
Autómata lineal con fronteraEs una tupla (Q, Σ, Γ, , B, A, δ)q0
conjunto finito de estados alfabeto de cadenas reconocidas alfabeto de cinta, estado inicial Símbolo de espacio en blanco pero estados finales
función de transición
QΣΓ Σ ⊂ Γq0B B ∈ Γ B ∉ ΣAδQ × Γ ∪ {<, >} → Q × Γ ∪ {<, >} × {der, izq}
Restricción, no se puede ir más allá de los símbolos <, >
s wt u v</</R
</</R
x/x/R
a/x/R
a/a/R
x/x/R x/x/R
b/x/R
b/b/Rb/b/L
c/x/L
a/a/L
c/c/L
x/x/L
</</R
Autómata de doble pila*Es una tupla (Q, Σ, Γ, , , A, δ)q0 Z0
conjunto finito de estados alfabeto de cadenas reconocidas alfabeto de pila estado inicial símbolo inicial de la pila
estados finales función de transición
QΣΓq0Z0Aδ Q × (Σ ∪ {ϵ}) × Γ × Γ → Q × ×Γ∗ Γ∗
Un AFND- + dos pilasϵ
a,Zo/BZo,CZo
a,B/BB,C/CC
b,B/ε,C/C
Z0
Z0
b,B/ε,C/C
q0 q1 q2 q3c,Zo/Zo,C/ε
c,Zo/Zo,C/ε
ε,Zo/Zo,Zo/Zo
Jerarquía de ChomskyLenguaje Gramática Máquina Ejemplo
Dependiente delcontexto
Tipo 1 ( )
Autómatalineal confrontera
Independientedel contexto
Tipo 2 ( )
Autómata depila
Regular Tipo 3 ( )
Autómatafinito
αV β → αγβww, anbncn
V → αw ,wr anbn
V → aA|ϵw, a∗
AF, AFNDAFND-ɛ
L
Verdadero
Falso
R
LLCAP, APD
ALFLDC
[email protected] ivanvladimir.github.io ivanvladimir
Revisando la jerarquía de Chomsky by is licensedunder a
. Creado a partir de la obra en
.
Ivan V. Meza RuizCreative Commons Reconocimiento 4.0 Internacional
License
http://turing.iimas.unam.mx/~ivanvladimir/slides/lfya/chomsky.html