Naloge 3. sklopa

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

Zapišite gramatiko za jezik besed, ki se začnejo na n a-jev in nadaljujejo na m b-jev in je n/=m. Besede, ki pripadajo jeziku so npr. abbb, aaabb, aabbbbb, itd. Besede, ki pa ne pripadajo jeziku so npr. prazna beseda, ab, aabb, aaabbb, abababa, itd.
To naredite postopoma.
a) Najprej napišite gramatiko, kjer dovolite imeti več a-jev kot b-jev.
b) Nato napišite gramatiko, kjer dovolite imeti več b-jev kot a-jev.
c) Združite ti dve gramatiki in dobite željeni rezultat.

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).

Last modified: Thursday, 8 May 2014, 8:29 PM