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

Сколько существует строк длины $n$ над алфавитом $A=\left\{ a_{1}, a_{2}, \ldots , a_{k}\right\}$, где $n$ — неотрицательное целое число?

Для строк $x$ и $y$ выполняется $(x y)^{R}=y^{R} x^{R}$.

Решите уравнение в словах

над алфавитом $\left\{ 0,1\right\}$; то есть найдите множество строк $x$ над $\left\{ 0,1\right\}$, удовлетворяющих этому уравнению.

Язык $\left\{ 0,10\right\}^{*}$ — это множество всех двоичных строк, не содержащих подстроки 11 и заканчивающихся на 0.

Покажите, что для любых языков $A$ и $B$

$A^{+}=A^{*}$ тогда и только тогда, когда $\varepsilon \in A$.

Для языков $A$ и $B$ выполняется $(A B)^{R}=B^{R} A^{R}$ и $(A \cup B)^{R}= A^{R} \cup B^{R}$.

(Лемма Ардена). Предположим, что $A, B$ — два языка, причём $\varepsilon \notin A$, и $X$ — язык, удовлетворяющий соотношению $X=A X \cup B$. Тогда $X=A^{*} B$.

Предположим, что языки $A, B \subseteq \left\{ a, b\right\}^{*}$ удовлетворяют следующим двум уравнениям:

Найдите простые представления для $A$ и $B$.

Пусть $A=\left\{ \text{ grand, }\varepsilon \right\}$ и $B=\left\{ \text{ mother, father }\right\}$. Чему равны $A B$ и $A^{*} B$?

Пусть $A$ — язык над $\left\{ a, b\right\}$, и $x \in \left\{ a, b\right\}^{*}$. Найдите необходимые и достаточные условия на $x$ и $A$, при которых выполняется уравнение

Для каждого из следующих уравнений определите, верно ли оно для всех языков $A, B$. Приведите доказательство или контрпример.

Докажите следующие тождества для языков $A, B, C, D$ :

Найдите кратчайшую строку над алфавитом $\left\{ 0\right\}$, которая не принадлежит $\left\{ \varepsilon , 0,0^{2}, 0^{5}\right\}^{3}$

Найдите общее решение уравнения

для $x, y \in \left\{ 0,1\right\}^{*}$.

Решите следующую систему языковых уравнений относительно языков $A, B, C \subseteq \left\{ a, b\right\}^{*}$ :

$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$.

Постройте $G(r)$ для $r=(11+0)^{*}(00+1)^{*}$.

Постройте $G(r)$ для $r=a^{*} b\left(c+d a^{*} b\right)^{*}$.

Какова кратчайшая строка в каждом из следующих языков? Какова кратчайшая непустая строка в каждом языке?

Найдите представления в виде размеченных орграфов для следующих регулярных выражений:

Определите регулярные выражения, представляемые орграфами на рисунке 1.7.

Рисунок 1.7: Три орграфа к упражнению 4.

Найдите простейший орграф, представляющий $\varepsilon$.

Найдите контрпримеры, показывающие, что теорема 1.25 неверна, если убрать требования о том, что $u$ должна быть нефинальной вершиной, а $v$ — неначальной вершиной.

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