Банк задач по математике

Задача 247

(а)(б)(в)

Определить конкатенацию для следующих пар языков $L_{1}$ и $L_{2}$ :

?

(а)

$L_{1}=\left\{ a, a b, a b b\right\}$ и $L_{2}=\left\{ \varepsilon , a, b, a b, b a\right\}$ ;

(б)

$L_{1}=\left\{ \varepsilon , a, a b, a b b\right\}$ и $L_{2}=\left\{ a, b, a b b, b a\right\}$ ;

(в)

$L_{1}=\left\{ \varepsilon , a, b, a b, a b a\right\}$ и $L_{2}=\left\{ \varepsilon , a, b, a b, b a\right\}$ .

Задача 248

(а)(б)(в)(г)

Пусть $L=\left\{ b a a, b a b, b b a, b b b\right\}$ . Какой из следующих языков является итерацией $L^{*}$ этого языка?

?

(а)

$\left\{ w: w=b w^{\prime } \text{ и } \left|w\right| \text{ делится на 3}\right\} \cup \left\{ \varepsilon \right\}$ ;

(б)

$\left\{ w: w=b w^{\prime } \text{ и } \left|w\right| \geqslant 3\right\} \cup \left\{ \varepsilon \right\}$ ;

(в)

$\left\{ w: w=x_{1} x_{2} x_{3} \ldots x_{3 n}, x_{i} \in \left\{ a, b\right\} \text{ и } x_{3 i+1}=b \text{ для всех }i<n\right\} \cup \left\{ \varepsilon \right\}$ ;

(г)

$\left\{ w: w=b w^{\prime } \text{ и } \left|w\right| \geqslant 12\right\}$ .

Задача 249

Доказать правильность регулярного выражения в примере 77 на стр. 316.

?

Задача 250

(а)(б)(в)(г)

Определить, какой язык представляется следующими выражениями:

?

(а)

$0^{*} 1^{*} 0$ ;

(б)

$01^{*} 0$ ;

(в)

$\left(01^{*}\right)^{*} 0$ ;

(г)

$\left(00+11+(01+10)(00+11)^{*}(01+10)\right)^{*}$ .

Задача 251

Доказать эквивалентности предложения 104 на стр. 315.

?

Задача 252

(а)(б)(в)(г)

Доказать следующие эквивалентности для регулярных выражений:

?

(а)

$p^{*}(p+q)^{*} \equiv p^{*}\left(q p^{*}\right)^{*} \equiv \left(p+q p^{*}\right)^{*} \equiv (p+q)^{*}$ ;

(б)

$p(q p)^{*} \equiv (p q)^{*} p$ ;

(в)

$\left(p^{*} q^{*}\right)^{*} \equiv \left(q^{*} p^{*}\right)^{*}$ ;

(г)

$(p q)^{+}\left(q^{*} p^{*}+q^{*}\right) \equiv (p q)^{*} p q^{+} p^{*}$ .

Задача 253

(а)(б)(в)(г)

Упростить следующие регулярные выражения:

?

(а)

$00^{*} 0+(00)^{*}$ ;

(б)

$(0+1)(\varepsilon +00)^{+}+(0+1)$ ;

(в)

$(0+\varepsilon ) 0^{*} 1$ ;

(г)

$\left(0^{*}+0\right)^{*}\left(01^{*}+0\right)$ .

Задача 254

С помощью эквивалентных преобразований регулярных выражений упростить результат $r$ , полученный в примере 81 на стр. 328.

?

Задача 255

(а)(б)(в)

Пусть $\mathfrak {N}_{r}$ — это автомат, который строится в доказательстве теоремы 111 на стр. 322 по регулярному выражению $r$ . Доказать следующие утверждения:

?

(а)

в диаграмме $\mathfrak {N}_{r}$ из каждой вершины выходит не более двух рёбер, а из принимающих — не более одного;

(б)

число состояний $\mathfrak {N}_{r}$ не более чем в три раза превосходит длину выражения $r$ , то есть $\left|Q\right| \leqslant 3\left|r\right|$ ;

(в)

при использовании оптимизированных методов число состояний $\mathfrak {N}_{r}$ не более чем в два раза превосходит длину выражения $r$ , то есть $\left|Q\right| \leqslant 2\left|r\right|$ .

Задача 256

Завершить доказательство предложения 110 на стр. 321, показать, что если $w \in \left(L\left(\mathfrak {M}_{1}\right)\right)^{*}$ , то $w \in L(\mathfrak {N})$ .

?

Задача 257

Применить процедуру детерминизации из теоремы 100 на стр. 302 и построить ДКА, эквивалентный HKA $\mathfrak {N}$ из примера 80 на стр. 323.

?

Задача 258

(а)(б)(в)(г)

Построить регулярное выражение, задающее язык $L$ в алфавите $\Sigma =\left\{ 0,1\right\}$ :

?

(а)

$L=\left\{ w: w\text{ содержит нечётное количество цифр 0 и чётное количество цифр 1}\right\}$ ;

(б)

$L=\left\{ w: w\text{ содержит подслово 001 или подслово 110}\right\}$ ;

(в)

$L=\left\{ w: w\text{ содержит по крайней мере два подряд идущих 0}\right\}$ ;

(г)

$L=\left\{ w: w\text{ не содержит подслов 011 и 010}\right\}$ .

Задача 259

Пусть $w$ — произвольное слово длины $k, m_{1}, \ldots , m_{n}$ — попарно различные натуральные числа, упорядоченные по возрастанию. Доказать, что язык $\left\{ w^{m_{1}}, \ldots , w^{m_{n}}\right\}$ можно описать регулярным выражением длины не большей $4 k m_{n}+4 n-7$ (с учётом всех необходимых по определению символов).

?

Задача 260

Выше в задаче 243 на стр. 310 предлагалось построить автомат, который проверяет правильность сложения. Построить регулярное выражение, задающее распознаваемый этим автоматом язык $S$ , то есть следующее множество слов в алфавите $\left\{ 0,1\right\}^{3}$ :

S = \left\{ \left\llbracket \begin{array}{l} a_{1} \\ b_{1} \\ c_{1} \end{array} \right\rrbracket \ldots \left\llbracket \begin{array}{l} a_{n} \\ b_{n} \\ c_{n} \end{array} \right\rrbracket \; : \; c_{n} \ldots c_{1}-\text{ сумма двоичных чисел } a_{n} \ldots a_{1} \text{ и } b_{n} \ldots b_{1}\right\}

?

Регулярные выражения