Минимальные детерминированные конечные автоматы

Пусть $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$ не является регулярным.

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

Постройте минимальные ДКА для языков, принимаемых ДКА на рисунках 2.52(a) и 2.52(b).

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

Постройте минимальный ДКА, эквивалентный НКА с рисунка 2.53.

Рисунок 2.53: НКА для упражнения 5.