Context-free grammars

Question 1

Kaj je KNG (Kontekstno neodvisna gramatika)?

Answer 1

KNG je končna množica spremenljivk. Spremenljivke so definirane rekurzivno z spremenljivkami in terminali. Pravila ki določajo spremenljivke, poimenujemo produkcije.

Question 2

Formalna definicija KNG (Kontekstno neodvisna gramatika)!

Answer 2

KNG - G = (V, T, P, S)
V - končna množica spremenljivk
T - končna množica terminalov
P - končna množica produkcij, kjer A -> a, kjer A ∊ V in a je beseda v jeziku (V U T)*
S - je posebna spremenljivka, ki jo kličemo začetni simbol

Question 3

Definicija jezika KNJ (Kontekstno neodvisni jezik)!

Answer 3

L(G) = {w | w ∊ T* IN Sg =>* w}

Question 4

Naštej lastnosti KNJ (Kontekstno neodvisni jezik)!

Answer 4

1. jezik L je KNJ, če L = L(g) za nek KNG G
2. nizu a ∊ (V U T)* rečemo sentencialna oblika, če Sg =>* a
3. G1 in G2 sta ekvivalentni, če L(G1) = L(G2)

Question 5

Definicija izpeljanjega drevesa!

Answer 5

Naj bo G = (V,T,P,S):

1. vsako vozlišče v ima oznako, ki je simbol v V U T U {ε}
2. oznaka korena je S
3. če je vozlišče notranjo in ima oznako A, potem A mora biti v V
4. če ima vozlišče v oznako A in so vozlišča v1, v2, …, vk “sinovi” od v z oznakami X1, X2, …, Xk, potem A -> X1, X2, …, Xk mora biti produkcija v P
5. Če ima vozlišče v oznako ε, potem je v “list” in je edini “sin” svojega “očeta”

Question 6

Teorem o Chomskijevi normalni oblik!

Answer 6

Vsak KNJ (Kontekstno neodvisni jezik) brez ε lahko generiramo z gramatiko v kateri je vsaka produkcija v obliki:
A -> BC ali A -> a, kjer so A,B,C spremenljivke, a pa terminal

Question 7

Teorem o Greibachovi normalni obliki!

Answer 7

Vsak KNJ brez ε lahko generiramo z gramatiko, v kateri je vsaka produkcija v obliki:
A -> bγ, kjer je A spremenljivka, b terminal in γ niz spremenljivk (γ ∊ V*)