Лекция 1

Question 1

Азбука

Answer 1

Крайно множество от символи (Σ).

Question 2

Буква

Answer 2

Елемент на азбуката Σ.

Question 3

Дума над Σ

Answer 3

Крайна редица от елементи на Σ.

Question 4

|α|

Answer 4

Дължина на думата α.

Question 5

Празна дума (ε)

Answer 5

Единствената дума с дължина 0, |ε| = 0.

Question 6

Σⁿ

Answer 6

Множеството от думите над Σ с дължина n.

Question 7

Σ⋆

Answer 7

Обединението на всички Σⁿ за n ≥ 0. Всички думи над Σ.

Question 8

Език L над Σ

Answer 8

Подмножество на Σ⋆.

Question 9

Индуктивна дефиниция за дума

Answer 9

ε е дума; ако β е дума и x ∈ Σ, то βx е дума.

Question 10

Конкатенация на думи

Answer 10

α · β = последователно залепване на α и β.

Question 11

Формално: α(βx) = (αβ)x

Answer 11

Индуктивна дефиниция на конкатенацията.

Question 12

Конкатенация на езици

Answer 12

A·B = {α·β | α ∈ A и β ∈ B}

Question 13

Итерация на език A

Answer 13

A⁰ = {ε}; Aⁿ⁺¹ = Aⁿ · A

Question 14

Звезда на Клини

Answer 14

A⋆ = ⋃ Aⁿ за n ≥ 0

Question 15

Детерминиран краен автомат (ДКА)

Answer 15

A = ⟨Σ, Q, qstart, δ, F⟩

Question 16

Функция δ

Answer 16

Q × Σ → Q (тотална функция на преходите)

Question 17

Разширена функция δ⋆

Answer 17

δ⋆(q, ε) = q; δ⋆(q, βx) = δ(δ⋆(q, β), x)

Question 18

Разпознат език L(A)

Answer 18

L(A) = {α ∈ Σ⋆ | δ⋆(qstart, α) ∈ F}

Question 19

Автоматен език

Answer 19

Съществува ДКА A, такъв че L = L(A)

Question 20

Конфигурация

Answer 20

Двойка (q, α) ∈ Q × Σ⋆ – текущо състояние и дума за четене.

Question 21

Релация ⊢A

Answer 21

Ако δ(q, b) = p, то (q, bα) ⊢A (p, α)

Question 22

Релация ⊢ᶫA

Answer 22

ℓ-стъпкова промяна: κ ⊢ᶫA κ′ ако κ се превръща в κ′ за ℓ стъпки.

Question 23

Релация ⊢⋆A

Answer 23

Рефлексивно и транзитивно затваряне на ⊢A.