2.5

Конечные автоматы и регулярные выражения

[7/43%]
Показать
LaTeX
Пример 2.29

Найдите ДКА, принимающий язык 10+(0+11)0∗110+(0+11) 0^{*} 1.

?
Пример 2.30

Постройте НКА, принимающий множество LL двоичных строк нечётной длины, содержащих подстроку 00.

?
Пример 2.32

Найдите регулярное выражение для языка, принимаемого НКА на рисунке 2.29(a).

?
Задача 2.5.1

Для каждого из следующих регулярных выражений rr постройте ДКА, принимающий L(r)L(r):

?
(a)

(0+10)∗(1+01)∗(0+10)^{*}(1+01)^{*}.

(b)

(0+1)∗0(0+1)(0+1)0(0+1)(0+1)^{*} 0(0+1)(0+1) 0(0+1).

(c)

0(0+1)∗0+1(0+1)∗10(0+1)^{*} 0+1(0+1)^{*} 1.

Задача 2.5.2

Для каждого из следующих языков найдите НКА, который его принимает:

?
(a)

{x#y∣x,y∈(0+1)∗,∣x∣≡∣y∣( mod 2)}\left\{ x \# y \mid x, y \in (0+1)^{*}, \left|x\right| \equiv \left|y\right|(\bmod 2)\right\}.

(b)

{x#y∣x,y∈(0+1)∗,∣x∣+∣y∣≥5}\left\{ x \# y \mid x, y \in (\mathbf{0}+\mathbf{1})^{*}, \left|x\right|+\left|y\right| \geq 5\right\}.

(c)

{x#y∣x,y∈(0+1)∗,∣x∣⋅∣y∣ делится на 5}\left\{ x \# y \mid x, y \in (\mathbf{0}+\mathbf{1})^{*}, \left|x\right| \cdot \left|y\right| \text{ делится на 5}\right\}.

Задача 2.5.3

На рисунке 2.41 показан НКА, принимающий 0∗0^{*}, построенный по методу примера 2.22. Четыре ε\varepsilon-перехода нельзя устранить по правилу теоремы 1.25. Примените метод из доказательства теоремы 2.31, чтобы сократить некоторые из его ε\varepsilon-переходов. Можете ли вы, исходя из этого примера, найти более общее правило (чем теорема 1.25) для устранения избыточных ε\varepsilon-переходов?

Рисунок 2.41: НКА, принимающий 0*.Рисунок 2.41: НКА, принимающий 0*.

?
Задача 2.5.4

Для каждого из языков, принимаемых НКА на рисунке 2.42, найдите регулярное выражение.

Рисунок 2.42: Два НКА для упражнения 4.Рисунок 2.42: Два НКА для упражнения 4.

?