IB102 - úkol 11
Odevzdání: 13.12. 2010
Vypracoval(a): Skupina:
UCO:
1. [2 body] Mejme nasledujúci gramatiku:
G = ({S1, 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 | y,
P	—	=,
E	-	V | N | E + E,
N	—	0 | 1 | 0N | IN,
C	—	ERE,
R	—	
Pro gramatiku G sestrojte syntaktický analyzator metodou shora dolů. Analyzujte slovo if x > 1 then y = 10.
Poznámka: Dobre si všimnete, jaka je množina terminýlu gramatiky, zejmena, ze ter-minaly jsou i znaky <, =, >, if a then. U posledních dvou jsme použili tuCne zvýraznení, abychom tím dali najevo, ze jde o jeden terminýl, nikoli o posloupnost dvou Ci Ctyr terminýlu. Bile misto (mezery) ve slove je jen pro lepsi citelnost, mezery nepatri mezi terminaly.
IB102 - úkol 11
Odevzdání: 13.12. 2010
Vypracoval(a): Skupina:
UCO:
2. [2 body] Mejme nasledujúci gramatiku:
G = ({S1, 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 | y,
P	—	=,
E	-	V | N | E + E,
N	—	0 | 1 | 0N | IN,
C	—	ERE,
R	—	
Pro gramatiku G sestrojte syntaktický analyzátor metodou zdolá náhoru. Analyzujte slovo if x > 1 then y = 10.
Poznámka: Dobre si všimnete, jaka je množina terminálu gramatiky, zejmena, ze ter-minaly jsou i znaky <, =, >, if a then. U posledních dvou jsme použili tuCne zvýraznení, abychom tím dali najevo, ze jde o jeden terminál, nikoli o posloupnost dvou Ci Ctyr terminálu. Bile misto (mezery) ve slove je jen pro lepsi citelnost, mezery nepatri mezi terminaly.
IB102 - úkol 11
Odevzdání: 13.12. 2010
Vypracoval(a): UCO: Skupina:
3. [2 body] Mejme nasledující jazyk nad abecedou {1, 2, 5, =}:
L = {x = y | x G {1, 2}*, y e {5}*, #^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íkovy automat akceptující jazyk L. Jasne uveď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 tlací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, neboť ta v sobe obsahuje i resení príkladu jako takoveho. Napísete-li tedy spravní zasobníkovy automat pro L s jedním stavem, získíte 4 body.)