Priklady k mid-term pisomke zo dna 4.4. a 7.4.2003 (6)
priklady z mid-term pisomky (3+3)
priklady (schema) zo zap. pisomiek (3+3)
nahr. priklady k zap. (5)

23.5., 11.4 2003

----------
priklady za mid-term pisomku 2003

Za kazde chybajuce 3 body 1 priklad.

1) Dokazte alebo vyvratte, ze nasledujuce jazyky su regularne
a) nad abecedou (a): L1 = set( a^p | p je prvocislo )
b) nad abecedou (a,b): 
	L2 = set( w | w obsahuje rovnaky (stejny) pocet slov "ab" a "ba" )
c) ako b), ale nad abecedou (a,b,c)

2) CH1.35 3,4
K automatu A
		a 	b
In/Out	1	2	1
	2	2	3
	3	4	3
	4	5	5
	5	1	5

a) skonstruujte ZNK automat pre jazyk La = set( uav | uv in L(A) ),
tj. jazyk zo slov L(A), do ktorych bol vlozeny prave jeden symbol a
b) zacnite tvorit ekvivalentny deterministicky automat zapisany stromom,
vytvorte aspon 15 (roznych) stavov.
c) Ako bude vyzerat automat pre jazyk (La zjednotenie L(A))

3) K RV (a(ab*a)*a)+lambda skonstruujte
a) zobecneny nedet. automat
b) det. automat
c) redukovany automat

4) Dokazte alebo vyvratte
a) L1\(L2 prienik L3) je nadmnozinou ((L1\L2) prienik (L1\L3))
b) L1\(L2 prienik L3) je podmnozinou ((L1\L2) prienik (L1\L3))
c) derivace_podla_w(Sigma* - L) = Sigma* - derivace_podla_w(L)

5) a) Vytvorte RV popisujuci prave vsetky slova nad (a,b), v ktorych
kazdy (maximalny) usek a-ciek ma parnu dlzku
b) zderivujte RV podla a, b, ab
c)vytvorte redukovany det. kon. automat

6) K automatu skonstruujte reg. vyraz.
		a 	b
In 	1	2	1
	2	2	3
out	3	2	1	

-----------------------------------------------------------------------
pisomka:
1) Ch1.34
a)K nedet automatu A skoonstruujte ekvivalentny automat, ktory prijima 
jazyk (L(A))^r (reverznych slov) - nakreslite graf

		a	b
In/Out	A 	A,C	B
	B	-	B,D
Out	C	-	-
	D	A	C,D

(varianta: D In)

b) Zostrojte ekvivalentny redukovany deterministicky kon. automat

2) Dokazte, ze L = set( a^(n^2) | n>=0 ) neni regularny

3) Dokazte alebo vyvratte
a) L1/(L2 prienik L3) je nadmnozinou ((L1/L2) prienik (L1/L3))
b) L1/(L2 prienik L3) je podmnozinou ((L1/L2) prienik (L1/L3))
varianta
   (L1 prienik L2)\L3 je nad/pod-mnozinou ((L1\L3) prienik (L2\L3))
---------------------
zap. 
1) Prevedte do Chomskeho NF. 4 neterm, X-> lambda
2) Zaradte do Chomskeho hierarchie co najnizsie jazyk prefixnych zapisov 
absolutne vyvazenych stromov
	a) je v triede L_X
	b) nie je v triede L_Y
3) navrhnite red. det. KA, vo w ex. abb alebo baa 
('a' nasledovane bezprostredne 'bb' alebo b nasledovane 'aa')
--
1) Prevedte do Greibachovej NF.; dtto
2) zaradte do ch.h.: {w| kazdy prefix w ma (ostro) viac 'a' nez 'b'}
3) navrhnite (ideu) nedet. zas. aut. pre jazyk L={ucv| u/=v, u,v in {a,b}* }
--
?

-------------
Priklady na zapocet: 5 (27.5.2003 16:15)
Podmienky: 
priklad 1) povinne, 3 z dalsich 4 prikladov (spravne)
(v.2 17:00) AK mate aspon z jednej pisomky 6 (resp. 9) a viac bodov, 
mozete si odpustit este jednu (resp. dve z roznych prikladov) 
podulohy z 1a,1b,2a,2b,5a,5b (a jeden cely z 2-5)


1) Nad abecedou {a,b}:
a) Vytvorte redukovany DKA pre jazyk slov, ktore obsahuju abaa a neobsahuju babb.
b) -''-: slova (ab+ba)* s najviac jednou chybou, tj. vypustenim alebo pridanim pismena.

2) a) Navrhnite obecnu (monotonnu) gramatiku pre jazyk L AVL stromov v prefixnom zapise.
Abeceda je {b,a,n}, vnutorne vrcholy su 'b', platne listy su 'a' s hlbkou 1 
a neexistujuce listy su 'n' s hlbkou 0. 
Vnutorne vrcholy 'b' maju aspon 1 platny podstrom ( bnn nie je v ziadnom slove).
Pre kazdy vrchol AVL stromu plati, ze hlbka laveho a praveho podstromu 
sa lisi najviac o 1.
priklad: ban, bbaabna su v L
bbnan nie je v L (poruseny root: lavy hlbky 2, pravy 0) 
b) dokazte , ze jazyk z 2a) nie je bezkontextovy 

3) Pre kazdy z jazykov:
a) obecnych binarnych stromov 
b) absolutne vyvazenych binarnych stromov
c) AVL stromov
zapisanych v prefixnom tvare nad {a,b,n} (viz 2) definujte 
jazyky La, Lb a Ln, tak aby pre vhodne definovane jazyky S(n) stromov hlbky bud 
i) prave n alebo 
ii) najviac n 
platilo pre vhodnu substituciu S(n+1) = S(n){a/La,b/Lb,n/Ln} pre n>0.
  Su niektore z definovanych substitucii homomorfizmy? 

4) a) Navrhnite schemu det. zas. automatov, ktore  realizuju kontrolu dobre 
uzatvorkovanych vyrazov s n druhmi zatvoriek a textom 't' (a la XML). 
b) Upravte automaty 
tak, aby sa v ramci jednej zatvorky nemiesal text a podzatvorky.

5) Zaradte do CHomskeho hierarchie jazyk (slov tvaru)
a) {b-z | b je binarny zapis k z N a z je unarny zapis k, tj. k-krat znak #}
	nad abecedou {0,1,-,#}
b) {b-z | b je binarny zapis k z N a z je reverzny zapis k v stvorkovej sustave}
	nad abecedou {0,1,2,3,-}
	prikl. slov: 0-0, 1-1, 10-2, 11-3, 100-01, 101-11, ...

---- a ine
ad zap 5) c) aby cely vyraz bol v jednej zatvorke
ad zap 6) c) z je reverzny zapis v trojkovej sustave
(99) (Ch1.?) navrhnite ideu automatov, ktore synchronizuju radu strelcov.