Irz kolokvij 2

Question 1

Naj bo G(V, T, P, S) KNG kaj so V, T, P, S?

Answer 1

V - končna množica spremenljivk (ne-terminalov)
T - končna množica terminalov
P - Končna množica produkcij, oblike A –> α in α je beseda iz jezika (V ∪ T)*
S - začetna spremenljivka

Question 2

Kontekstno neodvisna gramatika generira kontekstno neodvisni jezik. DRŽI ali NE DRŽI

Answer 2

DRŽI

Question 3

Zapišite strogo definicijo jezika L(G), ki ga generira gramatika G(V, T, P, S)

Answer 3

L(G) = {w | w ∈ T* ∧ S (G?)==>* w}

Question 4

Kdaj sta G1 in G2 ekvivalentna?

Answer 4

Gramatiki G1 in G2 sta ekvivalentni, kadar je jezik , ki ga generirata G1 in G2 enak.
L(G1) = L(G2)

Question 5

Kakšne so oblike produkcije gramatike v normalni obliki Chomskega?

Answer 5

A –> BC
A –> a
Kjer A ∧ B ∧ C ∈ V in a ∈ T

Question 6

Kakšne so oblike produkcije gramatike v normalni obliki Greibachove?

Answer 6

A –> aα
Kjer A ∈ V,
a ∈ T,
α je (lahko tudi prazno) zaporedje spremenljivk (V)

Question 7

Kdaj rečemo, da je gramatika G(V, T, P, S) dvoumna?

Answer 7

Kadar obstaja več kot eno drevo izpeljave oz. ko obstaja več kot ena sama leva izpeljava (ali več kot ena desna izpeljava)

Question 8

Vsak kontekstno neodvisen jezik brez prazne besede generira neka gramatika, ki je v normalni obliki Chomskega. DRŽI ali NE DRŽI

Answer 8

DRŽI

Question 9

Vsak kontekstno neodvisen jezik brez prazne besede generira neka gramatika, ki je v normalni obliki Greibachove. DRŽI ali NE DRŽI

Answer 9

DRŽI

Question 10

Naj bo M = (Q, Σ, Γ, δ, q0, Z0, F) skladovni avtomat. Kaj so Q, Σ, Γ, δ, q0, Z0, F?

Answer 10

Q - Končna množica stanj
Σ - Vhodna abeceda
Γ- Skladovna abeceda
δ - Funkcija prehodov
q0 - Začetno stanje, q0 ∈ Q
Z0 - Start simbol (simbol, ki se nahaja na vrhu sklada), Z0 ∈ Γ
F - Množica končnih stanj, F ⊆ Q

Question 11

Napiši definicijo δ funkcije za skladovni avtomat

Answer 11

δ: Q x (Σ ∪ {ε}) x Γ se mapira v končne podmnožice Q x Γ*

Question 12

Kako je definiran jezik, ki ga sprejme skladovni avtomat M = (Q, Σ, Γ, δ, q0, Z0, F)

Answer 12

Za skladovni avtomat definiramo 2 jezika:

L(M), ki je sprejet s končnim stanjem
L(M) = {w ∈ Σ* | (q0, w, Z0) Ͱ* (qF, ε, γ) ∧ qF ∈ F ∧ γ ∈ Γ*}

N(M), ki je sprejet s spraznitvijo sklada
L(M) = {w ∈ Σ* | (q0, w, Z0) Ͱ* (p, ε, ε) za p ∈ Q}

Question 13

Jezik je kontekstno neodvisen natakno tedaj, ko ga sprejme nek skladovni avtomat DRŽI ali NE DRŽI

Answer 13

DRŽI

Question 14

Razred jezikov, ki jih sprejmejo deterministični skladovni avtomati, je razred jezikov, ki jih sprejemajo nedeterministični skladovni avtomati. DRŽI ali NE DRŽI

Answer 14

NE DRŽI

Question 15

Za katere operacije je zaprt razred kontekstno neodvisnih jezikov?

Answer 15

• unija
• konkatenacija,
• kleenovo zaprtje
• substitucija
• homomorfizem
• obratni komomorfizem

Question 16

Napiši pogoje za deterministečen M = (Q, Σ, Γ, δ, q0, Z0, F)

Answer 16

Da je PDA determinističen, morata veljati 2 pogoja za vsak q ∈ Q in Z ∈ Γ:

1. δ(q, ε, Z) ≠∅ ==> ∀a ∈ Σ: δ(q, a, Z) = ∅
2. ∀a ∈ Σ ∪ {ε} : |δ(q, a, Z)| ≤ 1