Kontekstno neodvisne gramatike

Naloga 1

Podano imate gramatiko:

S⟶aSb|A

A⟶aA|ε

a) Zapišite množico spremenljivk in množico končnih simbolov.

b) Zapišite izpeljavo besede aaaabb v tej gramatiki.

c) Zapišite drevo izpeljave besede aaaabb v tej gramatiki.

d) Zapišite 5 najkrajših besed, ki so v jeziku te gramatike.

e) Zapišite 5 najkrajših besed, ki niso v jeziku te gramatike.

f) Z besedami opišite kakšen jezik generira ta gramatika.

Naloga 2

Zapišite gramatiko, ki generira vse možne nize sestavljene iz simbolov a 
in b.

a) Koliko produkcij ima ta gramatika?

b) Ali lahko zapišete gramatiko za isti jezik, ki ima 5 produkcij?

*c) Poiščite en niz, ki ga lahko v gramatiki zapisani pod točko b), izpeljemo na vsaj dva različna načina. Zapišite dve izpeljavi tega niza.

Naloga 3

Naloga 4

Podano imate dvoumno gramatiko izrazov:

E⟶E+E|E∗E|(E)|1|2| 3

a) S tremi drevesi izpeljav pokažite kako lahko generiramo izraz 2+1+3+1. Kakšno vrednost dobimo, če izraz izračunamo pri različnih drevesih izpeljave?

b) Zapišite tri različna drevesa izpeljave za izraz 2*1+3*2. Kakšne vrednosti dobimo, če izračunamo vrednost izraza z vsakim drevesom izpeljave?

Sedaj si pa poglejmo še gramatiko, ki pravilno izpelje izraze glede na prioritete (začetni simbol je E):

E⟶E+T

T⟶T∗F

F ⟶ (E)|1|2|3

c) Zapišite drevo izpeljave za izraz 2*1+3*2. Ali obstaja več dreves izpeljav?

d) Zapišite drevo izpeljave za izraz 2*3*(3+2).