Stvrta sada domacich uloh

Uloha 1

(odovzdavacia uloha)

Zostrojte BEZKONTEXTOVU gramatiku pre jazyk (nad abecedou {a,b})

     L = {w | # w = # w}
               a     b

Nezabudnite formalne dokazat, ze navrhnuta gramatika je gramatikou pre
jazyk L.
Poznamka: # , resp. #  znamena pocet pismen a, resp. b v slove w.
           a         b

Uloha 2

(odovzdavacia uloha)

Standardnou konstrukciou vytvorte ku gramatike G=(N,{a,b,c,d},P,S)
s mnozinou neterminalov N={S,A,B,C,D,E} a mnozinou pravidiel
P={S->aBS|DSc|c; A->DS|ABa; B->ba|aBa|BAD; C->CE|Ea|d; D->BA|DcD; E->cCd|bbc}
prislusnu redukovanu gramatiku.

Uloha 3

Dana je regularna gramatika G=(N,T,P,S). Zostrojte regularnu gramatiku G'=
(N',T,P',S') taku, aby pre jazyk L(G') platilo                   R
                                                   L(G') = [L(G)] 

Uloha 4

Zostrojte gramatiku co najjednoduchsieho typu pre jazyk

L = { w | # w = 1 (mod 3) a zaroven # w = 1 (mod 2) }, kde
           a                         b

w je slovo nad abecedou {a,b}.

Uloha 5

Standardnou konstrukciou zostrojte bezkontextovu gramatiku nepouzivajucu
epsilon pre jazyk dany gramatikou:

S -> aAabAb | aSaBC | aSbb | DD
A -> ABB | aBA | bb
B -> SABa | SbS | CC | a
C -> CB | CA | CS | epsilon
D -> DAD | aba

Uloha 6

Zostrojte bezkontextovu gramatiku pre mnozinu vsetkych takych aritmetickych
vyrazov v PASCALe, ktore pouzivaju len operatory +, -, * a /, pricom ako
operandy pouzivaju len premenne s identifikatormi a alebo b.

Uloha 7

Dokazte o kazdej z nasledujucich gramatik, ci je jednoznacna alebo viacznacna:

a) S -> SS | aSb | ab
b) S -> SS | aSb | epsilon
c) S -> AB
   A -> Aa | bAa | a
   B -> aB | aBc | a
   

Uloha 8

Popiste mnozinouvou notaciou (alebo presne slovne) jazyk generovany gramatikou:

S -> aSS | b