Лекция 10

Question 1

E-множество

Answer 1

E = {A ∈ V | A ⇒* ε} – променливи, извеждащи празната дума.

Question 2

Премахване на ε-правила

Answer 2

Включват се всички комбинации на изтриване на променливи от E от дясната страна на правилата.

Question 3

Ren

Answer 3

Ren = {(A,B) ∈ V×V | A ⇒* B} – релация на преименуване.

Question 4

Премахване на дълги правила

Answer 4

A → X1X2…Xk се заменя с A → X1A1, A1 → X2A2, …, Ak−2 → Xk−1Xk.

Question 5

Нормална форма на Чомски

Answer 5

Правила от вида A → BC или A → a, където A,B,C ∈ V, a ∈ Σ.

Question 6

Теорема 4

Answer 6

Всеки КС език без ε има граматика в Чомска нормална форма, която го генерира.

Question 7

CYK алгоритъм

Answer 7

Алгоритъм за проверка на принадлежност на дума към език, описан с граматика в Чомска нормална форма.

Question 8

Лема 5

Answer 8

A ⇒* aiai+1…ai+s ⇔ ∃B,C ∈ V, ∃k: A → BC, B ⇒* aiai+1…ak, C ⇒* ak+1…ai+s.

Question 9

Недетерминиран стеков автомат

Answer 9

P = ⟨Q,Σ,Γ, ♯,∆, qstart, qaccept⟩ – автомат с вход, стек и преходи, дефинирани чрез ∆.

Question 10

Конфигурация на стеков автомат

Answer 10

Тройка (q, α, γ), където q е състояние, α е оставащ вход, γ е съдържание на стека.

Question 11

Работа на P

Answer 11

Преход чрез четене или ε-преход, с възможност за замяна на върха на стека.

Question 12

L(P)

Answer 12

Множество от думи, при които (qstart, α, ♯) ⊢* (qaccept, ε, ε).