Лекция 7

Question 1

Алгоритъм за минимизация

Answer 1

Изчисляване на ≡A чрез последователни апроксимации ≡0A ⊇ ≡1A ⊇ … ⊇ ≡nA, стабилизираща до ≡A.

Question 2

Рекурентна формула за ≡n+1

Answer 2

p ≡n+1A q ⇔ p ≡nA q и δ(p, x) ≡nA δ(q, x) за всички x ∈ Σ.

Question 3

Сложност на алгоритъма за минимизация

Answer 3

Груба оценка: O(|Q|³); с оптимизация: O(|Q|²).

Question 4

Дефиниция 1

Answer 4

Неограничена граматика: G = (V, Σ, R, S), където R ⊆ (V ∪ Σ)+ × (V ∪ Σ)*.

Question 5

Дефиниция 3

Answer 5

L(G) = {ω ∈ Σ* | S ⇒*G ω} – език, генериран от граматиката G.

Question 6

Контекстна граматика

Answer 6

Граматика, чиито правила имат вида λAρ → λαρ с A ∈ V и α ∈ (V ∪ Σ)+.

Question 7

Регулярна граматика

Answer 7

Граматика, чиито правила са от вида A → aB и A → ε.