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

$a^{*}(a+b)^{*}=\left(a+b a^{*}\right)^{*}$.

$(ba)^{+}\left(a^{*} b^{*}+a^{*}\right)=(b a)^{*} b a^{+} b^{*}$.

Найдите регулярное выражение для множества двоичных представлений целых чисел, являющихся степенями 4.

Найдите регулярное выражение для множества двоичных строк, содержащих хотя бы одно вхождение подстроки 001.

Найдите регулярное выражение для множества $A$ двоичных строк, не содержащих подстроки 001.

Найдите регулярное выражение для множества $B$ всех двоичных строк, содержащих не более одной пары последовательных 0 и не более одной пары последовательных 1.

Найдите регулярное выражение для множества всех двоичных строк, обладающих тем свойством, что ни один из их префиксов не содержит на два 0 больше, чем 1, и ни один — на два 1 больше, чем 0.

Найдите регулярное выражение для множества всех непустых строк над арабскими цифрами, не содержащих повторяющихся соседних символов.

Найдите регулярное выражение для множества всех строк над алфавитом

которые представляют корректные операции сложения над двоичными представлениями целых чисел, с добавлением ведущих 0 при необходимости. Например, соотношение

означает, что строка

принадлежит этому множеству.

Для каждого языка $L$ над алфавитом $\Sigma$ пусть $L^{\prime }$ — множество всех суффиксов строк из $L$, то есть $L^{\prime }=\left\{ w \mid u w \in L\text{ для некоторой строки }u\right\}$. Покажите, что если $L$ — регулярный язык, то и $L^{\prime }$ тоже регулярен.

Покажите, что каждый регулярный язык обладает регулярным выражением в дизъюнктивной нормальной форме $\alpha_{1}+\alpha_{2}+\cdots +\alpha_{n}$, в котором каждое $\alpha_{i}$, для $i=1,2, \cdots , n$, не содержит оператора + .

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

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

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

Покажите, что $\left(0^{2}+0^{3}\right)^{*}=\left(0^{2} 0^{*}\right)^{*}$.

Постройте регулярное выражение для множества всех строк над алфавитом

которые представляют корректные операции вычитания. Например,

означает, что строка

принадлежит этому множеству.

Покажите, что для любого регулярного языка $L, L_{\text{odd}}=\left\{ x \in L \mid \left|x\right|=\text{нечётно}\right\}$ и $L_{\text{even}}=\left\{ x \in L \mid \left|x\right|=\text{чётно}\right\}$ являются регулярными.

Покажите, что если $L$ — регулярный язык, то $L^{\prime \prime }=\left\{ u \mid \exists v, u v \in L\right\}$ также регулярен.

Пусть $h: \Sigma^{*} \rightarrow \Gamma^{*}$ — отображение, удовлетворяющее условию $h(x y)=h(x) h(y)$ для любых $x, y \in \Sigma^{*}$. Покажите, что если $A$ — регулярное множество над $\Sigma$, то $h(A)=\left\{ h(x) \mid x \in A\right\}$ является регулярным множеством над $\Gamma$. Обратно, если $B$ — регулярное множество над $\Gamma$, то $h^{-1}(B)=\left\{ x \in \Sigma^{*} \mid h(x) \in B\right\}$ является регулярным множеством над $\Sigma$.