Formalne gramatike i jezici - ispitni zadaci

1. Ako je data gramatika G=( {S,A,B}, {a,b,?}, P, S} sa pravilima iz skupa P:

S->A?B
A->aB|?
B->bA|?

odrediti koje od sledećih niski pripadaju skupu L(G):

1. aba?bab
2. aba???bab
3. a?b
4. ???

 2. Ako je data gramatika G=( {S,A,B}, {x,y,*}, P, S} sa pravilima iz skupa P:

S->A*B
A->xB|*
B->yA|*

odrediti koje od sledećih niski pripadaju skupu L(G):

1. xx**yy
2. x*y*x*y
3. ***
4. xxx**yyy*

3. Ako je data gramatika G=( {S,A,B}, {a,b,c}, P, S} sa pravilima iz skupa P:

S->AcB
A->aB|c
B->bA|c

odrediti koje od sledećih niski pripadaju skupu L(G):

1. abacbab
2. acb
3. ccc