Конечные автоматы

Рассмотрим ДКА $M=\left(Q, \Sigma , \delta , q_{0}, F\right)$, где $Q=\left\{ q_{0}, q_{1}, q_{2}\text{, }q_{3}\right\} , \Sigma =\left\{ 0,1\right\} , F=\left\{ q_{1}, q_{2}\right\}$, а $\delta$ — функция, заданная следующей таблицей:

Начертите диаграмму переходов $M$.

Рассмотрим ДКА $M$, заданный на рисунке 2.2. Определите, принимает ли $M$ строки 000 и 010.

Какой язык $L(M)$ принимается ДКА $M$ на рисунке 2.2?

Какой язык $L(M)$ принимается ДКА $M$ на рисунке 2.3?

Какой язык $L(M)$ принимается ДКА $M$ на рисунке 2.4?

Рассмотрим ДКА $M$ с диаграммой переходов на рисунке 2.5.

Для целых чисел $n, d \geq 1$ рассмотрим ДКА $M_{n, d}=\left(Q, \Sigma , \delta , q_{0}, F\right)$, где $Q= \left\{ q_{0}, q_{1}, q_{2}, \cdots , q_{n-1}\right\} , \Sigma =\left\{ a_{0}, a_{1}, \cdots , a_{d-1}\right\} , \delta \left(q_{i}, a_{k}\right)=q_{(d i+k) \bmod n}$, а $F=\left\{ q_{1}\right\}$.

Для каждого из ДКА $M_{1}, M_{2}$ и $M_{3}$, показанных на рисунке 2.6(a), (b) и (c) соответственно, опишите словами язык, принимаемый им.

$(0+1)^{*}$.

Множество всех двоичных строк, начинающихся с префикса 01.

Множество всех двоичных строк, содержащих подстроку 00.

Множество всех двоичных строк, содержащих подстроку 00101.

Множество $A$ всех двоичных строк, заканчивающихся на 01.

Множество всех двоичных представлений положительных целых чисел, сравнимых с нулём по модулю 5.

Множество всех двоичных строк, содержащих подстроку 00 или заканчивающихся на 01.

Множество всех двоичных строк, содержащих подстроку 00 и заканчивающихся на 01.

Множество всех двоичных строк, содержащих подстроку 00, но не заканчивающихся на 01.

Множество $L$ всех двоичных строк, в которых каждый блок из четырёх подряд идущих символов содержит подстроку 01.

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

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

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

Найдите НКА, принимающий множество двоичных строк, содержащих подстроку 010.

Найдите НКА, принимающий множество двоичных строк, начинающихся с 010 или заканчивающихся на 110.

Найдите НКА, принимающий множество двоичных строк, содержащих не менее двух вхождений подстроки 01 и заканчивающихся на 11.

Рисунок 2.22: Решение примера 2.19.

Найдите НКА, принимающий множество $\left\{ 0^{n} 10^{m} \mid n, m \geq 0, n \equiv m(\bmod 5)\right\}$.

Пусть $M_{1}$ и $M_{2}$ — два НКА. Постройте НКА $M$ такой, что $L(M)=L\left(M_{1}\right) \cdot L\left(M_{2}\right)$.

Пусть $M_{1}$ — НКА. Постройте НКА $M$ такой, что $L(M)= L\left(M_{1}\right)^{*}$.

Рассмотрим НКА $M$ на рисунке 2.26.

Для каждого НКА $M$, показанного на рисунке 2.27, определите, чему равен $L(M)$.

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

Докажите, что новое начальное состояние $s$ и заключительное состояние $f$ в построении примера 2.22 необходимы. То есть найдите НКА $M_{1}$ и $M_{2}$ такие, что НКА $M_{1}^{\prime }$ и $M_{2}^{\prime }$ на рисунке 2.28 обладают свойством $L\left(M_{1}^{\prime }\right) \neq L\left(M_{1}\right)^{*}$ и $L\left(M_{2}^{\prime }\right) \neq L\left(M_{2}\right)^{*}$.

Дан НКА $M=\left(Q,\left\{ 0,1\right\} , \delta , q_{0}, F\right)$, где $Q=\left\{ q_{0}, q_{1}, q_{2}\text{, }q_{3}, q_{4}, q_{5}\right\} , F=\left\{ q_{3}, q_{4}\right\}$, и

(Диаграмма переходов $M$ показана на рисунке 2.29(a).) Найдите ДКА, эквивалентный НКА $M$.

Рисунок 2.29: Преобразование НКА в ДКА.

Постройте ДКА, эквивалентный НКА $M=(\left\{ p, q\text{, }r\right\} ,\left\{ 0,1\right\} , \delta , p,\left\{ q, r\right\} )$, где

Пусть $M=(\left\{ p, q, r, s\right\} ,\left\{ 0,1\right\} , \delta , p,\left\{ q, s\right\} )$ — $N F A$, заданный

Постройте НКА, принимающий $\overline{L(M)}$.

Постройте ДКА, принимающий множество всех двоичных строк, у которых пятый символ справа равен 0.

Рассмотрим следующую таблицу умножения на $\left\{ a, b, c\right\}$ :

Для любой строки $w$ из $\left\{ a, b, c\right\}^{+}$ через $\operatorname {value}(w)$ обозначим значение, полученное перемножением символов строки $w$ слева направо. Например, пусть $w=a b c b$. Тогда получаем

Постройте НКА для множества $L$ всех строк $w$ над $\left\{ a, b, c\right\}$ таких, что $\operatorname {value}(w)=\operatorname {value}\left(w^{R}\right)$. (Например, $a b c b \in L$, а $a b b \notin L$.)

Преобразуйте каждый из следующих НКА в эквивалентный ДКА:

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

Рассмотрим следующую таблицу умножения на $\left\{ a, b, c\right\}$ :

Постройте НКА для следующих языков:

Найдите ДКА, принимающий язык $10+(0+11) 0^{*} 1$.

Постройте НКА, принимающий множество $L$ двоичных строк нечётной длины, содержащих подстроку 00.

Найдите регулярное выражение для языка, принимаемого НКА на рисунке 2.29(a).

Для каждого из следующих регулярных выражений $r$ постройте ДКА, принимающий $L(r)$:

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

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

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

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

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

Пусть $M$ — некоторый $N F A$. Постройте $N F A M^{\prime }$, такой что $L\left(M^{\prime }\right)= L(M)^{R}$.

Пусть $f$ — подстановка над $\Sigma$. Пусть $L \subseteq \Sigma^{*}$ — регулярный язык, и для каждого $a \in \Sigma$ язык $f(a)$ регулярен. Тогда $f(L)$ также является регулярным языком.

Покажите, что для любого языка $L_{2}$, если $L_{1}$ регулярен, то $L_{1} / L_{2}$ также регулярен.

Пусть $L$ — регулярный язык над $\Sigma$, $k$ — положительное целое число, а $\phi$ — отображение из $\Sigma^{k}$ в $\Sigma$. Докажите, что

регулярен.

Докажите, что если $L$ регулярен, то регулярен и $\operatorname {MIN}(L)$.

Покажите, что если $A$ и $B$ — регулярные языки над $\left\{ 0,1\right\}$, то

также регулярен.

Покажите, что если $L$ — регулярный язык, то регулярен и

Покажите, что если $L$ — регулярный язык, то регулярен и

Покажите, что если $L$ — регулярное множество, то регулярно и

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

также регулярен.

Покажите, что если $L$ регулярен, то регулярен и

Докажите следующее тождество:

Для любых двух битов $a, b \in \left\{ 0,1\right\}$, $a \oplus b$ обозначает исключающее ИЛИ $a$ и $b$; то есть $0 \oplus 0=1 \oplus 1=0$ и $0 \oplus 1=1 \oplus 0=1$. Для любых двух двоичных строк $x$ и $y$ с $\left|x\right|=\left|y\right|$, $x \oplus y$ обозначает поразрядное исключающее ИЛИ строк $x$ и $y$. Например, если $x=0011$ и $y=0101$, то $x \oplus y=0110$. Пусть $A=001(0+1)^{*}$ и $B=(0+1)^{*} 100$. Найдите регулярное выражение для каждого из следующих языков:

Покажите, что если $A$ и $B$ — регулярные языки, то регулярны и следующие языки:

Приведите альтернативное доказательство примера 2.42, основанное на следующей идее: мы можем моделировать НКА $\bar{M}$ на $x y$ вместе с $\widehat{M}_{i}$ на $z$, моделируя на каждом шаге два перехода $\bar{M}$ и один переход $\widehat{M}_{i}$. (Таким образом, новый НКА для $L_{\frac{3}{3}}$ имеет всего $n+2$ дорожки.)

Покажите, что если $A$ и $B$ — регулярные языки, то регулярны и следующие:

Рассмотрим булеву функцию $f\left(a_{1}, a_{2}, \cdots , a_{n}\right)$. Для любых $n$ двоичных строк $x_{1}, x_{2}, \cdots , x_{n}$ одинаковой длины обозначим через $f\left(x_{1}, x_{2}, \cdots , x_{n}\right)$ поразрядное применение функции $f$ к $x_{1}, x_{2}, \cdots , x_{n}$. То есть, если $x_{i}=x_{i_{1}} x_{i_{2}} \ldots x_{i_{k}}$ для $i=1,2$, $\ldots , n$, где каждый $x_{i_{j}}$ — бит из $\left\{ 0,1\right\}$, то $f\left(x_{1}, x_{2}, \ldots , x_{n}\right)$ равно

Покажите, что если языки $A_{1}, A_{2}, \cdots , A_{n}$ регулярны, то язык

также регулярен.

В упражнении 3(c) выше покажите, что для любого регулярного языка $A$ число различных $A_{x}$ конечно. Найдите верхнюю оценку для этого числа, предполагая, что $A$ принимается ДКА с $s$ состояниями.

Верны ли следующие утверждения? Докажите или опровергните ваш ответ.

Покажите, что каждый регулярный язык в $0^{*}$ можно представить в виде

для некоторых целочисленных констант $a_{1}, a_{2}, \cdots , a_{k}, b_{1}, b_{2}, \cdots , b_{h}$ и $c$.

Подмножество $P$ неотрицательных целых чисел является в конечном счёте периодическим, если существуют два положительных целых числа $b, p$, такие что для всех $m \geq b$ из $m \in P$ следует $m+p \in P$. Докажите следующие утверждения:

Примените упражнение 10(d) выше, чтобы доказать следующие результаты:

Пусть $L=\left\{ x \in (0+1)^{*} \mid \left|x\right|\text{ нечётно}\right\}$. Найдите все классы эквивалентности отношения $R_{L}$.

Пусть $L$ — множество непустых двоичных строк, начинающихся и заканчивающихся одним и тем же символом. Найдите все классы эквивалентности отношения $R_{L}$.

Покажите, что $L$ регулярен тогда и только тогда, когда существует положительное целое $k$, такое что $x R_{L} y$ тогда и только тогда, когда для каждого $z \in \Sigma^{*}$ с $\left|z\right| \leq k$, $x z \in L \Leftrightarrow y z \in L$.

Найдите минимальный ДКА для языка $(0+1)^{*} 01$.

Постройте минимальный ДКА для языка $(0+1)^{*} 0(0+1)^{9}$.

Найдите минимальный ДКА, эквивалентный ДКА $M$ с рисунка 2.47.

Рисунок 2.47: ДКА M.

Покажите, что следующий язык не является регулярным:

Покажите, что $L=\left\{ 0^{m} 1^{n} \mid \operatorname {gcd}(m, n)=1\right\}$ не является регулярным.

Для произвольного языка $L$ определим отношение эквивалентности $D_{L}$ следующим образом:

Покажите, что $L$ регулярен тогда и только тогда, когда $\operatorname {Index}\left(D_{L}\right)<\infty$.

Найдите все классы эквивалентности отношения $R_{L}$ для следующих языков:

Для каждого из следующих языков $L$ покажите, что $\operatorname {Index}(L)=\infty$, и, следовательно, $L$ не является регулярным.