Лекция 2

Question 1

Регулярен израз

Answer 1

Израз, конструиран с ∅, ε, букви от Σ, както и с операции събиране (+), конкатенация (·) и звезда на Клини (⋆).

Question 2

Регулярен език

Answer 2

Език L ⊆ Σ⋆, за който съществува регулярен израз r такъв, че L = L(r).

Question 3

Затвореност на автоматните езици

Answer 3

Класът на автоматните езици е затворен относно булевите операции: обединение, сечение, допълнение, разлика, симетрична разлика.

Question 4

Краен език

Answer 4

Всеки език, съдържащ краен брой думи. Всеки краен език е автоматен.

Question 5

Регулярен израз ∅

Answer 5

Описва езика L(∅) = ∅.

Question 6

Регулярен израз ε

Answer 6

Описва езика L(ε) = {ε}.

Question 7

Регулярен израз a (a ∈ Σ)

Answer 7

Описва езика L(a) = {a}.

Question 8

Операция + при регулярни изрази

Answer 8

Ако r1 и r2 са регулярни изрази, то L(r1 + r2) = L(r1) ∪ L(r2).

Question 9

Операция · при регулярни изрази

Answer 9

Ако r1 и r2 са регулярни изрази, то L(r1 · r2) = L(r1) · L(r2).

Question 10

Звезда на Клини при регулярни изрази

Answer 10

Ако r1 е регулярен израз, то L(r⋆1) = L(r1)⋆.