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\left|x, y \in (0+1)^{*},\left|x\right| \equiv \right| y \mid (\bmod 2)\right\}.

(b)

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

(c)

{x#y∣x,y∈(0+1)∗,∣x∣⋅∣y∣ is dividable by 5}\left\{ x \# y\left|x, y \in (\mathbf{0}+\mathbf{1})^{*},\left|x\right| \cdot \right| y \mid \text{ is dividable by 5}\right\}.

Задача 2.5.3

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

(Теорема 1.25: Пусть rr — регулярное выражение. Тогда ε\varepsilon-ребро (u,v)(u, v) в G(r)G(r), являющееся единственным исходящим ребром из нефинальной вершины uu или единственным входящим ребром в неначальную вершину vv, можно стянуть в одну вершину, сохранив при этом свойство теоремы 1.23. Если один из концов ε\varepsilon-ребра является начальной или конечной вершиной, то таковой является и получившаяся вершина.)

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

?
Задача 2.5.4

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

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

?