Недетерминированные машины Тьюринга

$L_{1}=\left\{ a^{i_{1}} b a^{i_{2}} b \cdots b a^{i_{k}} \mid i_{1}, i_{2}, \ldots , i_{k} \geq 0, k \geq 3, i_{r}=i_{s}=i_{t}\text{ для некоторых }1 \leq r<s<t \leq k\right\}$.

$L_{2}=\left\{ x_{1} c x_{2} c \cdots c x_{m} c c y \mid x_{1}, \ldots , x_{m}, y \in \left\{ a, b\right\}^{*},\left(\exists i_{1}, \ldots , i_{k}\right)[1 \leq \left.i_{1}<\cdots <i_{k} \leq m, x_{i_{1}} x_{i_{2}} \cdots x_{i_{k}}=y\right]\right\}$.

Регулярное выражение $r$ называется беззвёздным регулярным выражением, если оно не содержит символ * (звезду Клини). Покажите, что задача определения того, не эквивалентны ли два беззвёздных регулярных выражения $r_{1}$ и $r_{2}$ (то есть, верно ли $L\left(r_{1}\right) \neq L\left(r_{2}\right)$), принадлежит $\mathrm{NP}$.

Покажите, что задача определения того, не эквивалентны ли два регулярных выражения, принадлежит $\operatorname {NSPACE}(n)$.

Расширенное регулярное выражение — это регулярное выражение, в котором может использоваться дополнительная операция пересечения (обозначаемая $\cap$). Покажите, что задача определения того, не эквивалентны ли два расширенных регулярных выражения, принадлежит $\bigcup_{c>0} \operatorname {NSPACE}\left(2^{c n}\right)$.

Покажите, что лемма 6.31 по-прежнему верна, если заменить условия $s_{2}(n) \geq n$ и $f(n) \geq n$ на $s_{2}(n) \geq \log n$ и $\log (f(n))= O\left(s_{2}(n)\right)$. [Подсказка: заметим, что НМТ $M_{3}$ может моделировать $M_{2}$ на входе $y=x S^{f(\left|x\right|)-\left|x\right|}$, не выписывая строку $y$ на второй ленте. Вместо этого она может просто записывать на второй ленте позицию $k$ головки входной ленты $M_{2}$ и использовать $k$, чтобы определить, какой входной символ сканирует головка ленты $M_{2}$.]

Покажите, что для любых вещественных чисел $r>0$ и $0<\epsilon <1$,

Покажите, что $E X P \neq \mathrm{NP}$.

Покажите, что EXP $\neq \bigcup_{c>0} \operatorname {DTIME}\left(2^{n^{c}}\right)$.