Příklad
M = ({q0, P, f}, {a, b}, {A, B, Z}, S, q0,Z, {f}),
S(q0,a,Z) = {(q0,AZ)} S(q0,a,A) ={(q0,AA)} S(q0,a,B) = {(q0,AB)} ó(q0,b,Z) = {(q0,BZ)} S(q0,b,A)={(q0,BA)} ó(q0,b,B) = {(q0,BB)} ô(q0,e,Z)={(p,Z)} 6{qo,e,A) ={{p,A)} ó(q0,s,B)={(p,B)} 6{p,a,A) ={{p,e)} ô(p,b,B) ={{p,e)} 5{p,e,Z) ={(f,Z)}
IB102 Automaty, gramatiky a složitost, 27.10.2014
Příklad
M = ({q0}, {a, b}, {Z, A}, ó, q0, Z, 0), kde
S(q0,a,Z) = {(q0,A)} S(q0,a,A) ={(q0,AA)} 6{q0,b,A) = {(q0,£)}
IB102 Automaty, gramatiky a složitost, 27.10.2014
2/27
Ekvivalence dvou způsobů akceptování
Věta 3.39. Pro každý jazyk L platí:
L = L(M) pro nějaký PDA M L = Le(M) pro nějaký PDA M
Důkaz, koncový stav => prázdný zásobník Intuice:
K danému J\f zkonstruujeme M simulující jeho činnost.
Vejde-li J\f do koncového stavu, M se nedeterministicky rozhodne
■ pokračovat v simulaci automatu M nebo
■ přejít do nově přidaného stavu q£, v němž vyprázdní zásobník.
IB102 Automaty, gramatiky a složitost, 27.10.2014
3/27
Komplikace:
Řešení: Před zahájením simulace bude u M na dně zásobníku symbol, který nedovolíme odstranit jinde, než ve stavu q£.
IB102 Automaty, gramatiky a složitost, 27.10.2014
Konstrukce: Nechť N = (Q, Z, r, 5, qb, 2b, F).
Klademe M = (Q U {g0, ge}, Z, r U {2'}, «$', qrQ, 2', 0), kde Z' £ r, g0, ge ^ Q a <5' je definována takto:
■ W0,e,Z') = {(q0,2b^)}
■ jestliže S(q, a, 2) obsahuje (r, 7), pak <5'(qf, a, 2) obsahuje (r, 7)
■ S'(q,e,Z) obsahuje {q£,Z)
pro všechny     FaZe Tu {2'}
■ <J'(ge,e,Z) = {{q£,e)} pro všechny Ze ru {2'}
IB102 Automaty, gramatiky a složitost, 27.10.2014
5/27
Korektnost:
IB102 Automaty, gramatiky a složitost, 27.10.2014
prázdný zásobník =>- koncový stav Intuice:
K danému M zkonstruujeme M simulující jeho činnost.
■ M si před simulací přidá na dno zásobníku nový symbol.
■ Je-li M schopen číst tento symbol (tj. zásobník automatu M je prázdný) tak M přejde do nově přidaného stavu qf, který je koncovým stavem.
IB102 Automaty, gramatiky a složitost, 27.10.2014
7/27
Konstrukce: Nechť M = (Q,   r, 5, q0,Z0,0).
Klademe JV=(Qu {q&, g>}, Z, r U {Z'}, 5', <£, Z', {q,}), kde Z' ^ r, q'Q, qf £ Q a 5' je definována takto:
■ W0,e,Z') = {(q0,Z0Z')}
■ jestliže 5(q, a, Z) obsahuje (r, 7), pak 8'(q, a, Z) obsahuje (r, 7)
■ á'(q,£,Z') = {(qf,£)} pro všechny q e Q
IB102 Automaty, gramatiky a složitost, 27.10.2014
Grafická reprezentace konfigurací
IB102 Automaty, gramatiky a složitost, 27.10.2014
9/27
Rozšířený zásobníkový automat
Definice 3.44. Rozšířený zásobníkový automat je sedmice
U = (Q,E,r,<J,qb,2b,F), kde
■ všechny symboly až na ô mají tentýž význam jako v definici PDA,
■ S je zobrazením
z konečné podmnožiny množiny Q x (Z u {e}) x r* do konečných podmnožin množiny Q x r*.
Pojmy konfigurace a akceptovaný jazyk (koncovým stavem, prázdným zásobníkem) zůstávají beze změny. Krok výpočtu |-^- definujeme takto:
do f
(p,aw,7la) h=- (q, w,72a) <=^> 3(q, 72) g <J(p, a, 71) pro a g Z u {e}
IB102 Automaty, gramatiky a složitost, 27.10.2014
10/27
Příklad
n = {{q0, p, f}, {a, b, c, d}, {A, B, Z}, ó, q0,Z,
ô{q0,a,e) ={(qr0,^)}
6{qo,b,e) ={(q0,B)}
S(q0,e,e) ={(p,e)}
S(p,a,A) ={{p,e)}
ô(p,b,B) ={{p,e)}
6{p,c,AA) ={{p,e)}
ó(p,c,BBB) = {(p,e)}
5{p,d,Z) ={(f,e)}
IB102 Automaty, gramatiky a složitost, 27.10.2014
Ekvivalence rozšířených PDA a PDA
Lemma 3.45. Ke každému rozšířenému PDA existuje ekvivalentní (obyčejný) PDA.
Intuice:
IB102 Automaty, gramatiky a složitost, 27.10.2014
12/27
Důkaz. Nechť TZ = (Q, Z, r, 5, q0, Z0, F) je rozšířený PDA a
m = max{|a| | 5(q, a, a) je definováno pro nějaké q e Q,aelu {e}}.
Definujeme V = (Q^, Z, V^5^,q:,Z:, F:), kde
■ d = {[q, a] | qre Q, a g Pf, 0 < |a| < m}, m r-] = r u {Z,}, kde Z| je nový symbol,
■ gi =[q0,Z0Z1m-1],
■ F-i = {[q, a] | g g F, a g ľ*, 0 < |a| < m}.
IB102 Automaty, gramatiky a složitost, 27.10.2014
13/27
■ <5i je definována takto:
- jestliže S(q, a, X-\... Xk) obsahuje (r, Y-\... Y/), pak
/> k: 6i{[q,Xi ...Xka],a,Z) obsahuje ([r,/3],7Z), kde /37 = V, ... Y,a a |/3| = m, pro všechny ZeHaaer] takové, že \a\ = m -
I < k: <5i        .. .X^a], a, Z) obsahuje ([r,    ... Y/aZ],í pro všechny Z g n a a g    takové, že |a| = m -
- ^([g.aJ.e.Z) = {([q,aZ\,e)} pro všechny g g Q, Z g n a a g    takové, že \a\ < m
IB102 Automaty, gramatiky a složitost, 27.10.2014
Korektnost: Ověříme, že platí
(q,aw,X,...XkXk+,...Xn)^r(r, w,Y,...Y,Xk+,...Xn) <=^ ([q,a],aw,/3)[^-([r,a'],w,l3'),
kde
□ aí3 = X,...XnZ™,
B a>í3> =Y,...YlXk+:...XnZ™, Q \a\ = \a'\ = m a
□ mezi dvěma výše uvedenými konfiguracemi PDA V neexistuje taková konfigurace, kde druhá komponenta stavu (tj. buffer) by měla
délku m. □
IB102 Automaty, gramatiky a složitost, 27.10.2014
15/27
Zásobníkové automaty a bezkontextové jazyky
	Lemma 3.45	PDA		PDA
rozšířené		akceptující	Věta 3.39	akceptující
				
PDA		koncovým		prázdným
	triviálně			
		stavem		zásobníkem
CFG
IB102 Automaty, gramatiky a složitost, 27.10.2014
16/27
Zásobníkové automaty a bezkontextové jazyky
Motivace 1: Jaká je třída jazyků rozpoznávaných zásobníkovými automaty?
Motivace 2: Je dána bezkontextová gramatika Q a slovo w. Jak zjistit, zda se slovo w dá vygenerovat v gramatice Q?
Problém syntaktické analýzy pro bezkontextové gramatiky:
pro danou bezkontextovou gramatiku Q a slovo w rozhodnout, zda w g L(G).
IB102 Automaty, gramatiky a složitost, 27.10.2014
17/27
Ekvivalence bezkontextových gramatik a zásobníkových automatů
Věta 3.51. Ke každému PDA M lze sestrojit CFG Q takovou, že Le(M) = L(Q).
Důkaz. Vynechán. □
Věta 3.47. Ke každé CFG G lze sestrojit PDA M takový, že L(G) = Le(M).
Důkaz. Uvedeme za chvíli. □
Důsledek 3.52. Třída jazyků rozpoznávaných zásobníkovými automaty je právě třída bezkontextových jazyků.
IB102 Automaty, gramatiky a složitost, 27.10.2014
18/27
Intuice převodu PDA na CFG
1. 10| = 1
IB102 Automaty, gramatiky a složitost, 27.10.2014
19/27
Intuice převodu PDA na CFG
2. |Q| > 2
IB102 Automaty, gramatiky a složitost, 27.10.2014
20/27
Intuice převodu CFG na PDA
Konstrukce PDA řeší problém syntaktické analýzy. (Platí pro dané G a w: w e /.(£)?)
w g L(Q) <;=>- v Q existuje derivační strom s výsledkem w
IB102 Automaty, gramatiky a složitost, 27.10.2014
21/27
Intuice převodu CFG na PDA aneb O nedeterministické syntaktické analýze
PDA se bude snažit budovat derivační strom pro w.
shora dolů
zdola nahoru
IB102 Automaty, gramatiky a složitost, 27.10.2014
22/27
Intuice pro analýzu shora dolů
Budování derivačního stromu simuluje levé derivace, tj. vždy rozvij nejlevější neterminál.
IB102 Automaty, gramatiky a složitost, 27.10.2014
Nedeterministická syntaktická analýza shora dolů
Věta 3.47. Ke každé CFG G lze sestrojit PDA M takový, že L{Q) = Le(M).
Důkaz. K dané gramatice Q konstruujeme PDA M, který simuluje levé derivace v Q.
■ V levé derivaci je v jednom kroku odvození nahrazen (nejlevější) neterminál A pravou stranou X-\ ... Xn nějakého /A-pravidla.
■ V M této situaci odpovídá náhrada A na vrcholu zásobníku řetězem Xi ... Xn.
M = ({q}, Z, N u Z, ô, q, S, 0), kde ô je definována:
■ S(q, e, A) obsahuje (q, a) právě když /I-íbgP
■ S(q, a, a) = {(q, e)} pro všechna a g Z
IB102 Automaty, gramatiky a složitost, 27.10.2014
24/27
S aAB
A ->• Aa | e B     SaA I b
ó(q,e,S) = {(q, aAB)}
ô{q,e,A) = {{q,Aa),{q,s)}
ô(q,e,B) = {(q, SaA), (q, b)}
ô(q,a,a) = ô(q,b,b) = {{q, e)}
S aAB
=> aB =>- aSaA =>- aaABaA => aaBaA => aabaA => aaba
IB102 Automaty, gramatiky a složitost, 27.10.2014
25/27
Korektnost
A^* w ^  (q,w,A) H^(q,e,e)
(=>) Indukcí vzhledem k délce odvození m. m m = 1: zřejmé.
■ m > 1: nechť tvrzení platí pro všechna ni < m.
A    X-\X2 ... Xk     x-\x2 ... xk = w, kde X\ ^ x-,,0 < m-, < m z definice ô plyne (q, w,A) |—(q, w,X-\X2 .. .Xk).
Je-li Xj g N, pak dle indukčního předpokladu máme
(q,Xj,Xj) [í-(q,e,e).
Je-li Xj g Z, pak Xt = x, a z definice á plyne (q, x(, x() |— (q, e, e). Kompozicí dostáváme (g, w, /A)      (q, e, e).
IB102 Automaty, gramatiky a složitost, 27.10.2014
26/27
{<=) Předpokládejme (q, w, A) |— (q, e, e) a ukažme A =>" Indukcí vzhledem k délce výpočtu n. m n = 1: zřejmé.
■ n > 1: nechť tvrzení platí pro všechna ní < n. (q,w,A) \-(q,w,X,Xz...Xk), tj. A    X,X2 ... Xk
w můžeme napsat jako w = x-|X2... xk takové, že
■ je-li Xj g N, pak (q, x-„ Xj)      (q, e, e), kde n-, < Dle IP Xj ^+ Xj.
■ je-li Xj g Z, pak Xj => x(.
Vhodnou kompozicí obdržíme
A    X-\ X2 ... Xk ^* x-\ X2 ... Xk     x-i ... xk = w
což je levá derivace slova w v gramatice Q.
IB102 Automaty, gramatiky a složitost, 27.10.2014