Регулярные языки и конечные автоматы

$L_{1}=\left\{ a, a b, a b b\right\}$ и $L_{2}=\left\{ \varepsilon , a, b, a b, b a\right\}$;

$L_{1}=\left\{ \varepsilon , a, a b, a b b\right\}$ и $L_{2}=\left\{ a, b, a b b, b a\right\}$;

$L_{1}=\left\{ \varepsilon , a, b, a b, a b a\right\}$ и $L_{2}=\left\{ \varepsilon , a, b, a b, b a\right\}$.

$\left\{ w: w=b w^{\prime } \text{ и } \left|w\right| \text{ делится на } 3\right\} \cup \left\{ \varepsilon \right\}$;

$\left\{ w: w=b w^{\prime } \text{ и } \left|w\right| \geqslant 3\right\} \cup \left\{ \varepsilon \right\}$;

$\left\{ w: w=x_{1} x_{2} x_{3} \ldots x_{3 n}, x_{i} \in \left\{ a, b\right\} \text{ и } x_{3 i+1}=b \text{ для всех }i<n\right\} \cup \left\{ \varepsilon \right\}$;

$\left\{ w: w=b w^{\prime } \text{ и } \left|w\right| \geqslant 12\right\}$.

$(1+01)^{*}(\varepsilon +0)$;

$\left(1^{*} 01^{*}\right)^{*}$;

$(01)^{*} 1^{*} 01^{*}$;

$1^{*} 01(1+01)^{*}(\varepsilon +0)$;

$(1+01)^{*}(0+1)$;

$1^{*}\left(011^{*}\right)^{*}(\varepsilon +0)$.

$a(b a)^{*}$;

$(b a)^{*} b$;

$b^{*} a b^{*}$;

$b(a b+a b a b)^{*}$;

$(b a)^{*} b(a b)^{*}$;

$(a b+b a)^{*}$.

$\mathfrak {N}_{1}=\left(\left\{ q, p, r, s, t\right\} ,\left\{ 0,1\right\} , P_{1}, q,\left\{ t\right\} \right)$;

$\mathfrak {N}_{2}=\left(\left\{ q, p, r, s\right\} ,\left\{ 0,1\right\} , P_{2}, q,\left\{ s\right\} \right)$;

$\mathfrak {N}_{3}=\left(\left\{ q, p, r, s, t\right\} ,\left\{ 0,1\right\} , P_{3}, q,\left\{ s\right\} \right)$.

Программы автоматов заданы в таблице на рис. 29 (- означает отсутствие соответствующих переходов).

$\mathfrak {N}_{4}=\left(\left\{ q, p, r, s, t\right\} ,\left\{ 0,1\right\} , P_{4}, q,\left\{ t\right\} \right)$;

$\mathfrak {N}_{5}=\left(\left\{ q, p, r, s\right\} ,\left\{ 0,1\right\} , P_{5}, q,\left\{ p, r\right\} \right)$;

$\mathfrak {N}_{6}=\left(\left\{ q, p, r, s, t\right\} ,\left\{ 0,1\right\} , P_{6}, q,\left\{ p, r, s\right\} \right)$.

Программы автоматов заданы в таблице на рис. 30 на противоположной странице (- означает отсутствие соответствующих переходов).

$0^{*} 1^{*} 0$;

$01^{*} 0$;

$\left(01^{*}\right)^{*} 0$;

$\left(00+11+(01+10)(00+11)^{*}(01+10)\right)^{*}$.

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

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

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

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

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

$p^{*}(p+q)^{*} \equiv p^{*}\left(q p^{*}\right)^{*} \equiv \left(p+q p^{*}\right)^{*} \equiv (p+q)^{*} ;$

$p(q p)^{*} \equiv (p q)^{*} p$;

$\left(p^{*} q^{*}\right)^{*} \equiv \left(q^{*} p^{*}\right)^{*}$;

$(p q)^{+}\left(q^{*} p^{*}+q^{*}\right) \equiv (p q)^{*} p q^{+} p^{*}$.

$00^{*} 0+(00)^{*}$;

$(0+1)(\varepsilon +00)^{+}+(0+1)$;

$(0+\varepsilon ) 0^{*} 1$;

$\left(0^{*}+0\right)^{*}\left(01^{*}+0\right)$.

$L=\left\{ w: w\text{ содержит нечётное количество цифр 0 и чётное количество цифр 1}\right\}$;

$L=\left\{ w: w\text{ содержит подслово 001 или подслово 110}\right\}$;

$L=\left\{ w: w\text{ содержит по крайней мере два подряд идущих 0}\right\}$;

$L=\left\{ w: w\text{ не содержит подслов 011 и 010}\right\}$.

$r_{1}=a a(b b+a a)^{*} b b$;

$r_{2}=(a+b b)(a+b)^{*}(a a+b b)$;

$r_{3}=\left(a^{+}+b^{+}\right)(a b+b a)^{*}$;

$r_{4}=(a b b)^{*}\left(a a b^{*}+b b a^{*}\right)$;

$r_{5}=b^{*}\left(a b^{*} a\right)^{*} b^{*}$;

$r_{6}=(a b+b a)^{*}(a a+b b)^{*}$.

$r_{1}=a a(b a b)^{*} b b, r_{2}=a^{*}(b b a)^{*} b^{+}$;

$r_{1}=(b a)^{*}(a b b+b a)^{*}, r_{2}=(a b b)^{*}(a+b b)^{*}$;

$r_{1}=(b+a b)^{*}(a a+b)^{*}, r_{2}=(a b+b b)^{*}\left(a^{*}+b^{*}\right)$;

$r_{1}=b^{*}(a b+a b b)^{*}\left(a^{*}+b b^{*}\right), r_{2}=\left(b^{*}+(a b)^{*}\right)(b+a a)^{*}$.

$r_{1}=(b a)^{*}(b+a a)^{*}$;

$r_{1}=(a b)^{*}+(b a+b b a)^{*}$;

$r_{1}=(a a+a b)^{*}(b+a)^{*}$;

$r_{1}=(a+b)^{*} b(b a)^{*} b(b b)^{*}$.

$r_{1}=(b+a)(a+b b)^{*}$;

$r_{1}=(a+a b+a b b)^{*} b^{*}$;

$r_{1}=b^{*}(b b a+b a)^{*}$;

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

???

???

???

???