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

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

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

Доказать правильность регулярного выражения в примере 77 на стр. 316: выражение $(1+01+001)^{*}(\varepsilon +0+00)$ утверждается представляющим язык всех слов в алфавите $\{ 0,1\}$, не содержащих подслово «000».

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

Доказать эквивалентности предложения 104 на стр. 315: для любых регулярных выражений $r, q, p$

1. $r+p \equiv p+r$ (коммутативность объединения);

2. $(r+p)+q \equiv r+(p+q)$ (ассоциативность объединения);

3. $(r p) q \equiv r(p q)$ (ассоциативность конкатенации);

4. $(r^{*})^{*} \equiv r^{*}$ (идемпотентность итерации);

5. $(r+p) q \equiv r q+p q$ (дистрибутивность).

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

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

С помощью эквивалентных преобразований регулярных выражений упростить результат $r$, полученный в примере 81 на стр. 328: $r=(a a)^{*}+a(a a)^{*}\left(b a(a a)^{*}\right)^{*} b(a a)^{*}+a(a a)^{*}+a(a a)^{*}\left(b a(a a)^{*}\right)^{*} b a(a a)^{*}$.

Пусть $\mathfrak {N}_{r}$ — это автомат, который строится в доказательстве теоремы 111 на стр. 322 по регулярному выражению $r$ (теорема 111: для каждого регулярного выражения $r$ можно эффективно построить НКА, распознающий $L(r)$, индукцией по построению $r$ — фиксированный автомат для каждого базисного случая $\varnothing$, $\varepsilon$, $a \in \Sigma$, а по автоматам для $r_{1}$ и $r_{2}$ строится объединённый автомат для $r_{1}+r_{2}$, $r_{1} \& r_{2}$ и $r_{1}^{*}$ склейкой с новыми $\varepsilon$-переходами). Доказать следующие утверждения:

Завершить доказательство предложения 110 на стр. 321, показать, что если $w \in \left(L\left(\mathfrak {M}_{1}\right)\right)^{*}$, то $w \in L(\mathfrak {N})$, где $\mathfrak {M}_{1}$ — конечный автомат с начальным состоянием $q_{0}^{1}$ и единственным принимающим состоянием $q_{f}^{1}$, а $\mathfrak {N}$ получен из $\mathfrak {M}_{1}$ добавлением нового начального и единственного принимающего состояния $q_{0}$ вместе с двумя $\varepsilon$-переходами $q_{0} \xrightarrow {\varepsilon } q_{0}^{1}$ и $q_{f}^{1} \xrightarrow {\varepsilon } q_{0}$ (так что $L(\mathfrak {N})=(L(\mathfrak {M}_{1}))^{*}$ согласно предложению 110).

Применить процедуру детерминизации из теоремы 100 на стр. 302 (теорема 100: для каждого НКА $\mathfrak {N}$ можно эффективно построить такой ДКА $\mathfrak {M}$, что $L(\mathfrak {M})=L(\mathfrak {N})$) и построить ДКА, эквивалентный НКА $\mathfrak {N}$ из примера 80 на стр. 323.

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

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

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