Priklady k mid-term pisomke zo dna 4.4. a 7.4.2003
11.4.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))