IB102 - úkol 11 - řešení
Odevzdání: 13.12. 2010
Vypracoval: James Bond Skupina: MI6
UCO: 007
1. [2 body] Mejme následující gramatiku:
G = ({S', S, A, V, P, E, N, C, R}, {x, y, 1, 0, <, >, =, if, then,;, +}, P, S'), kde
S'	—	' S     ;   S      | S,
S	—	A | if C then S,
A	—	VPE,
V	—	x 1 y
P	—	
E	-	V | N | E + E,
N	—	0 | 1 | 0N | 1N,
C	—	ERE,
R	—	
Pro gramatiku G sestrojte syntaktický analyzátor metodou shora dolů. Analyzujte slovo if x > 1 then y = 10.
Rešeni: Syntaktický analyzator metodou shora dolu vypada takto:
Atd = ({q} {x, y, 1, 0, <, >, =if, then,; , +},
{x, y, 1, 0, <, >, =, if, then,;, +, S', S, A, V, P, E, N, C, R}, č, q, S', 0), kde
ó(q,e,S')	=	{(q, S'; S), (q, S)}	ó(q, x, x)	=	{(q,e)}
ó(q,£,S )	=	{(q, A), (q, if C then S)}	ó(q,y,y)	=	{(q,e)}
ó(q,e,A)	=	{(q, VPE)}	ó(q, 1, 1)	=	{(q,e)}
ó(q,e,V)	=	{(q,x)(q,y)}	ó(q, 0, 0)	=	{(q,e)}
ó(q,e,P)	=	{(q, =)}	ó(q,<,<)	=	{(q,e)}
ó(q,e,E)	=	{(q, V), (q, N), (q, E + E)}	ó(q,>,>)	=	{(q,e)}
ó(q,e,N)	=	{(q, 0), (q, 1), (q, 0N), (q, 1N)}	ó(q =, =)	=	{(q,e)}
ó(q,e,C)	=	{(q, ERE)}	ó(qif,if)	=	{(q,e)}
ó(q,e,R)	=	{(q =), (q,<^ (q,>)}	ó (q, then, then)	=	{(q,e)}
ó(q;,;)	=	{(q,e)}	ó(q, +, +)	=	{(q,e)}
Syntaktickou analýzou slova if x > 1 then y = 10 je pak nýsledující výpočet: (q, if x > 1 then y = 10, S') ^ (q, if x > 1 then y = 10, S)
j-^ (q, if x > 1 then y = 10, if C then S)
(q, x > 1 then y = 10, C then S)
if
^ (q,x> 1 then y = 10, ERE then S) ^ (q, x > 1 then y = 10, VRE then S)
(q,x > 1 then y = 10,xRE then S) ^ (q, > 1 then y = 10, RE then S) ^ (q, > 1 then y = 10, > E then S) \> (q, 1 then y = 10, E then S) ^ (q, 1 then y = 10, N then S)
(q, 1 then y = 10,1 then S)
(q, then y = 10, then S)
.then ,
I— (q,y =10,S) ^ (q,y =10, A) ^ (q,y = 10,VPE) ^ (q,y = 10,yPE) ^ (q, = 10,PE) (q, = 10, = E)
P- (q, 10, e )
^ (q, 10, N) ^ (q, 10,1N) \L (q, 0,N) ^ (q, 0,0)
p (q,e,e)
IB102 - úkol 11 - řešení
Odevzdání: 13.12. 2010
Vypracoval: James Bond UCO: 007
Skupina: MI6
2. [2 body] Mejme nasledujúci gramatiku:
G = ({S', S, A, V, P, E, N, C, R}, {x, y, 1, 0, <, >, =, if, then,;, +}, P, S'), kde
P = {
S'	—	S     ;   S      | S,
S	—	A | if C then S,
A	—	VPE,
V	—	x 1 y
P	—	=,
E	-	V | N | E + E,
N	—	0 | 1 | 0N | 1N,
C	—	ERE,
R	—	
Pro gramatiku G sestrojte syntaktický analyzátor metodou zdola nahoru. Analyzujte slovo if x > 1 then y = 10.
Rešeni: Syntaktický analyzator metodou zdola nahoru vypada takto:
Abu = ({q r}, (x,y 1, 0, <, >, =,if,then,;, +},
{x, y, 1, 0, <, >, =, if, then,;, +, S', S, A, V, P, E, N, C, R, _L}, í, q, L, {r}), kde
ó(q, x, e)	=	{(q,x)}	ó (q, e, S'; S)	= {(q, S')}
ó(q,y,e)	=	{(q,y)}	ó(q,e,S)	= {(q, S')}
	=	{(q,1)}	ó(q, e, A)	= {(q, S)}
ó(q 0,e)	=	{(q, 0)}	ó(q, e, if C then S)	= {(q, S)}
ó(q,<,e)	=	{(?,<)}	ó(q, e, VPE)	= {(q, A)}
ó(q,>,e)	=	{(q,>)}	ó( q, e, x)	= {(q, V)}
ó(q =,e)	=	{(q, =)}	ó(q,e,y)	= {(q, V)}
	=	{(q, if)}	ó(q, e, =)	= {(q, P), (q, R)} (!)
ó(q, then, e)	=	{(q, then)}	ó(q,e,V)	= {(q, E)}
ó(q;,e)	=	{(q,;)}	ó(q,e,N)	= {(q, E)}
ó(q +,e)	=	{(q,+)}	ó(q,e,E + E)	= {(q, E)}
ó(q,e 0)	=	{(q, N)}	ó(q, e, 1)	= {(q, N)}
ó(q,e, 0N)	=	{(q, N)}	ó(q,e, 1N)	= {(q, N)}
ó(q, e, ERE)	=	{(q, C)}	ó(q, e, <)	= {(q, R)}
í(q,e,>)	=	{(q, R)}	ó(q,e, _LS')	= {(r,e)}
Syntaktickou analýzou slova if x > 1 then y = 10 je pak nasledujúci výpočet:
(q, if x > 1 then y = 10, _L)      (q, x > 1 then y = 10, _Lif)
\^— (q, > 1 then y = 10, _Lif x)
^ (q,> 1 then y = 10, Lif V) (q,> 1 then y = 10, Lif E)
\> (q, 1 then y = 10, Lif E >) (q, 1 then y = 10, Lif ER)
^ (q, then y = 10, Lif ER1) (q, then y = 10, Lif ERN) (q, then y = 10, Lif ERE) (q, then y = 10, Lif C)
.then  , . „  „    , ,
\— (q,y = 10, Lif C then) (q, = 10, Lif C then y) (q, = 10, Lif C then V)
\= (q, 10, Lif C then V =) (q, 10, Lif C then VP)
^ (q, 0, Lif C then VP 1) (q,e, Lif C then VP 10) (q,e, Lif C then VP 1N) (q,e, Lif C then VPN) (q,e, Lif C then VPE) (q,e, Lif C then A) (q,e, Lif C then S)
^ (q,e, LS)
^ (q,e, LS') (r,e,e)
IB102 - úkol 11 - řešení
Odevzdání: 13.12. 2010
Vypracoval: James Bond UCO: 007
Skupina: MI6
3. [2 body] Mejme následující jazyk nad abecedou {1, 2, 5, =}:
L = {x = y | x G {1, 2}*, y G {5}*, #i(x) + 2 • #2(x) = 5 • #5(y)}
Jedna se tedy o jazyk vsech slov, ktera jsou tvaru x = y, kde x se skiada pouze ze znaku 1 a 2, y jen ze znaku 5 a ciferný soucet x a y je stejná. (Všimnete si, ze znak = patrí mezi znaky abecedy!)
Sestrojte zásobníková automat akceptující jazyk L. Jasne uved'te, jakám způsobem Vás automat akceptuje (koncovym stavem, prázdnám zasobníkem). (Motivace: jde o to, sestrojit automat, do nejz uzivatel hazá mnozstvá jedno- a dvoukorun, pak zmackne tlaďtko = a nasledne hazá mnozstvá petikorun. Automat ma rozhodnout, jestli castky vhozene pred a po zmacknutí tlaďtka = byly stejne.)
BONUS [+2 body]: Sestrojte zasobnáková automat s jednám stavem, akceptujácá jazyk L. (Stacá vyresit bonusovou variantu, nebot' ta v sobe obsahuje i resená pnkladu jako takoveho. Napásete-li tedy spravná zasobnákovy automat pro L s jednám stavem, záskáte 4 body.)
Rešení: Idea konstrukce bude takova, ze si automat bude poďtat ciferny soucet dosud prectenách 1 a 2 na zasobnáku (pomocá jednoho pomocneho symbolu X, jehoz pocet bude odpovádat cifernemu souctu), po prectem = prejde do noveho stavu, kde bude s kazdym dalsám symbolem 5 odeďtat pet symbolu X ze zásobnáku (k tomu budeme potrebovat pomocne stavy). Automat bude akceptovat koncovym stavem. Hledany zasobnákovy automat se pak da napsat napnklad takto:
2, Z) = {(qx,XXZ)}
í(qx, =,Z) = {(qy,Z)} Ó(qy, 5,X) = {(q4,£)} í(q3,£,X) = {(q2,£)} í(qi,e,X) = {(qy
í(qx, 1,X ) = {(qx,XX)} %x, 2, X) = {(qx,XXX)} %x, =,X ) = {(qy ,X)} í(q4,e,X) = {(q3,£)} í(q2,e,X) = {(qi,e)} ó(qy ,e,Z) = {(qF
Rešení bonusove varianty: Prvná idea zasobnákoveho automatu pro jazyk L s jedinym stavem bude taková, ze si vsechny informace budeme pamatovat na zasobnáku. Zásobnák bude opet slouzit jako poďtadlo, ale másto jednoho symbolu pouzijeme pet symbolu 1, 2, 3, 4, 5 s tám, ze vsechny symboly na zasobnáku krome vrcholoveho budou 5. Pri ctená symbolu = pak dovolíme pokracovat pouze tehdy, je-li na vrcholu zasobníku symbol 5 (a tedy hodnota poďtadla je delitelna peti). Nasledne budeme s kazdám ctenám symbolem 5 jeden symbol 5 vybárat ze záasobnáku.
Předchozí idea má ale drobný nedostatek - potřebujeme pro ni ve skutečnosti dva stavy (je třeba si pamatovat, jestli jsme před symbolem = nebo za ním). Toto se ale da obejít, a k tomu opet využijeme zýsobník: Budeme mít dve varianty symbolu 5: symboly 5 a V. Symbol 5 se bude vyskytovat pouze na vrcholu zasobníku, a to pouze tehdy, nebyl-li dosud čten symbol =. Ve vsech ostatních případech bude symbol 5 nahrazen symbolem V.
Automat bude samozrejme akceptovat prízdnym zasobníkem (mame-li jenom jeden stav, nemuzeme si dovolit akceptovat koncovím stavem).
Formalne se tedy da takovíto automat zapsat takto:
A = ({q}, {1, 2, 5, =}, {1, 2, 3, 4, 5, V, Z}, č, q, Z, 0), kde
	= {(q, 1)}	č(q, 2, Z)	= {(q, 2)}
č(q, 1,1)	= {(q, 2)}	č(q, 2,1)	= {(q, 3)}
č(q, 1,2)	= {(q, 3)}	č(q, 2, 2)	= {(q, 4)}
č(q, 1, 3)	= {(q, 4)}	č(q, 2, 3)	= {(q, 5)}
č(q, 1,4)	= {(q, 5)}	č(q, 2, 4)	= {(q, 1V)}
č(q, 1,5)	= {(q, 1V)}	č(q, 2, 5)	= {(q, 2V)}
č(q, =,Z)	= {(q,e)}	č(q, =, 5)	= {(q, V)}
č(q, 5, V)	= {(q,e)}