depende del contexto
Post on 11-Apr-2017
38 Views
Preview:
TRANSCRIPT
Depende del contexto
A veces te vas por las ramas para no tener que ir directo a la raíz. Sobre todo si la raíz es dolorosa ypuede derribar el árbol—Albert Espinosa
Ivan Meza
Jerarquía de ChomskyLenguaje Gramática Máquina
Independiente de contexto Tipo 2 ( )
Autómata de pila
Regular Tipo 3 ( )
Autómata finito
V → α
V → aA|ϵ
AF, AFNDAFND-ɛ
L Verdadero
FalsoR
AF, AFNDAFND-ɛ
L
Verdadero
FalsoR
LLCAP
Autómata de pilaEs una tupla (Q, Σ, Γ, , , A, δ)q0 Z0
Un AFND- + una pilaϵ
Autómata de piladeterminístico (APD)Es una tupla (Q, Σ, Γ, , , A, δ)q0 Z0
Para cada solo hay una transición, no más de unatransiciónSi , entonces , si existe trancisión , noexiste ningún otra más
δ(q, a, x)
δ(q, ϵ, x) ≠ ∅ δ(q, a, x) = ∅ ϵ
Lenguaje donde x = xr
Lenguaje donde x = xr
q₀ q₁ q₂a,Zo/Zo
b,B/εb,Z₀/BZ₀
a,B/AB
ε,Z₀/Z₀
Z0
a,Z₀/AZ₀
b,B/BB
b,Zo/Zo
a,B/Bb,B/B
a,A/Ab,A/A
b,A/BA
a,A/AAɛ,Zo/Zoɛ,A/Aɛ,B/B
a,A/ε
Más de una transición posibleCuando aparece para otro símboloϵ
No determinístico
Lenguaje donde xxr
Lenguaje donde xxr
q₀ q₁ q₂
b,B/εb,Z₀/BZ₀
a,B/AB
ε,Z₀/Z₀
Z0
a,Z₀/AZ₀
b,B/BBb,A/BA
a,A/AA
ɛ,Zo/Zoɛ,A/Aɛ,B/B
a,A/ε
Cuando aparece para otro símboloϵ
No determinístico
Lenguaje donde xmxr
Lenguaje donde xmxr
q₀ q₁ q₂
b,B/εb,Z₀/BZ₀
a,B/AB
ε,Z₀/Z₀
Z0
a,Z₀/AZ₀
b,B/BBb,A/BA
a,A/AA
m,Zo/Zom,A/Am,B/B
a,A/ε
Determinístico: APD
Resumen
, no determinístico no determinístico
determinístico
x = xr
xxr
xmxr
Las gramáticas
P → aPa|bPb|a|b|ϵP → aPa|bPb|aa|bbP → aPa|bPb|m
Ambigüedad y no determinismo es no determinístico, pero no es
ambiguoAP (x = )xr G(x = )xr
No determinismo tiene que ver con el proceso, ambigüedadcon la estructura
Usando un AP para simular un G
Dado , crear donde
G = (V , Σ, P , S) (Q, Σ, Γ, , , A, δ)q0 Z0
y Q = { , , }q0 q1 q2Γ = V ∪ Σ ∪ { }Z0 ∉ V ∪ ΣZ0A = { }q2
Producciones
Iniciar la pila y cancelar la pila
δ( , ϵ, ) = {( , S })}q0 Z0 q1 Z0δ( , ϵ, ) = {( , })}q1 Z0 q2 Z0
Producciones
Para manejar las producciones
Para todo , A ∈ V δ( , ϵ, A) = {( , α})|A → α}q1 q1δ( , a, a) = {( , ϵ})}q1 q1
q₀ q₁ q₂
ε,A/α|A∈V
ε,Z₀/Z₀
Z0
ε,Zo/SZo
a,a/ε |a∈Σy A α
P → aPa|bPb|a|b|ϵ
P → aPa|bPb|a|b|ϵ
q₀ q₁ q₂
ε,P/aPa
ε,Z₀/Z₀
Z0
ε,Zo/PZo
a,a/εb,b/ε
ε,P/bPbε,P/aε,P/bε,P/ε
Para todo podemos crear un G(L) AP (L)
¿Cual es su gramática?
q₀ q₁ q₂
b,B/εb,Z₀/BZ₀
a,B/AB
ε,Z₀/Z₀
Z0
a,Z₀/AZ₀
b,B/BBb,A/BA
a,A/AA
m,Zo/Zom,A/Am,B/B
a,A/ε
Transiciones se transforma a, A/α A → aα
Pushes:
Transiciones:
Pop:
Terminó:
→ aAZ0 Z0A → aAA
→ mZ0 Z0A → mA
A → a
→ ϵZ0
→ aAZ0 Z0→ bBZ0 Z0
A → aAAB → aABA → bBAB → bBB
→ mZ0 Z0A → mAB → mBA → aB → b
→ ϵZ0
Derivación abmba
⇒ aAZ0 Z0⇒ abBAZ0⇒ abmBAZ0⇒ abmbAZ0⇒ abmbaZ0⇒ abmba
Dado un AP podemos crear su Gequivalente
AP (L) = G(L)
¡Ahora si esta parte estácompleta!
Lenguaje Gramática Máquina
Independiente de contexto Tipo 2 ( )
Autómata de pila
Regular Tipo 3 ( )
Autómata finito
V → α
V → aA|ϵ
¿Hay algo afuera de LLC?
Lemma de bombeo para LLC
Proponer lenguajeEscoger Proponer una cadena que dependa de Particionar cadena en , tal que ,Checar que se cumplan restriccionesChecar si para todo está en el lenguaje
nn
uvwxy uwx < n |vx| ≥ 0
u w y ∈ Lvi xi i
Proponer lenguaje , que tal Escoger , que tal Proponer una cadena que dependa de Particionar cadena en , tal que ,
Caso uno en aes, Caso dos en aes y bes, Caso tres en bes y ces, Caso tres en ces,
En todos los casos existe una palabra que
akbkck
n nn anbncn
uvwxy uwx < n |vx| ≥ 0vwx aiaibncn
vwx aibicn
vwx anbici
vwx anbncici
∉ L
Lenguajes dependientes delcontexto
Sin contexto
Con contexto
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
S
S
cB
WB
WX
BX
bB
→→→→→→→
abc
aSBc
WB
WX
BX
Bc
bb
Derivación para aaabbbccc
S ⇒ aSBc⇒ aaSBcBc⇒ aaabcBcBc⇒ aaabWBcBc⇒ aaabWXcBc⇒ aaabBXcBc⇒ aaabbccBc
⇒ aaabbccBc⇒ aaabbcWBc⇒ aaabbcWXc⇒ aaabbcBXc⇒ aaabbcBcc⇒ aaabbWBcc⇒ aaabbWXcc⇒ aaabbBXcc⇒ aaabbBccc⇒ aaabbbccc
ivanvladimir@gmail.com ivanvladimir.github.io ivanvladimir
Depende del contexto by is licensed under 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/ldc.html
top related