Tretia sada domacich uloh

Uloha 1

                                         
Zostrojte (pomocou mnozin H ) mnozinu neterminalov
                           i
               *
 H = { X | S => xXy pre nejake slova x,y }, pricom X je z N

pre gramatiku G=(N,T,P,S), kde P pozostava z pravidiel

	S->aSb|bSA|c
	E->CA|EB|a
	A->SAB|SDb
	B->BA|SDD|b
	C->aSE|BA|a
	D->Sa|AB

Uloha 2

Zostrojte gramatiku co najjednoduchsieho typu (a pokuste sa zdovodnit, preco
jednoduchsia gramatika neexistuje) pre jazyk 
           i j i j 
     L = {a b c d  | i,j >= 0 }

Uloha 3

Zostrojte gramatiku co najjednoduchsieho typu (a pokuste sa zdovodnit, preco
jednoduchsia gramatika neexistuje) pre jazyk 
           i j j i
     L = {a b c d  | i,j >= 0 }

Uloha 4

Zostrojte gramatiku co najjednoduchsieho typu (a pokuste sa zdovodnit, preco
jednoduchsia gramatika neexistuje) pre jazyk 
     L = {ww | w je slovo nad abecedou {a,b} }

Uloha 5

Zostrojte KONTEXTOVU gramatiku pre jazyk (nad abecedou {1,#})
           i  j  i*j 
     L = {1 #1 #1    | i,j>=0}

Uloha 6

Zostrojte KONTEXTOVU gramatiku pre jazyk (nad abecedou {1,#})
           i  j 
     L = {1 #1  | i>0; j = dolna cela cast z log i }
                                                2