Замкнутость. Неавтоматные языки

Обращением слова $w=a_{1} a_{2} \ldots a_{k}, a_{i} \in \Sigma$ при $i=1, \ldots , k$, называется слово $w^{-1}=a_{k} \ldots a_{2} a_{1}$. Показать, что для автоматного языка $L$ его обращение — язык $L^{-1}=\left\{ w^{-1}: w \in L\right\}$ — также является автоматным. $\circledast$

Пусть $L$ — автоматный язык в алфавите $\Sigma$. Доказать, что автоматными являются и следующие языки:

Пусть $L$ — автоматный язык в алфавите $\Sigma =\left\{ a_{1}, \ldots , a_{m}\right\}$, а $L_{1}, \ldots , L_{m}$ — это автоматные языки в алфавите $\Delta$. Доказать, что автоматным является и язык $\operatorname {SUBST}(L)$, полученный из слов $L$ заменой каждой буквы $a_{i}$ на некоторое слово из $L_{i}$. Таким образом, $\operatorname {SUBST}(L)=\left\{ w_{1} w_{2} \ldots w_{n}: w_{1} \in L_{i_{1}}, \ldots , w_{n} \in L_{i_{n}} \text{ и существует } a_{i_{1}} a_{i_{2}} \ldots a_{i_{n}} \in L\right\}$. $\circledast$

Пусть $L_{1}$ — автоматный язык в алфавите $\Sigma$, а $L_{2}$ — произвольный язык в том же алфавите. Доказать, что язык

также является автоматным. $\circledast$

Тасовкой языков $L_{1}$ и $L_{2}$ называется язык

Здесь $x_{1}, \ldots , x_{n}, y_{1}, \ldots , y_{n}$ — произвольные слова. Доказать, что если языки $L_{1}$ и $L_{2}$ являются автоматными, то язык $\operatorname {SHUFFLE}\left(L_{1}, L_{2}\right)$ тоже будет автоматным. $\circledast$

Пусть язык $L$ в алфавите $\left\{ a, b, c\right\}$ состоит из всех слов, в которых количество букв $b$ превосходит количество букв $a$ не менее чем на 2. Предположим, что $L$ — автоматный язык, а $n$ — это константа, которая существует для него по утверждению леммы о разрастании. Какие из следующих «специальных» слов позволяют опровергнуть это предположение, то есть для какого из них не выполнено утверждение 3) леммы о разрастании?

Пусть язык $L$ в алфавите $\left\{ a, b\right\}$ состоит из всех слов нечётной длины, средней буквой в которых является $a$. Предположим, что $L-$ автоматный язык, а $n$ — это константа из леммы о разрастании. Какие из следующих «специальных» слов позволяют опровергнуть это предположение, то есть для какого из них не выполнено утверждение 3) леммы о разрастании?

Для каких из следующих языков $L$ в алфавите $\Sigma =\left\{ a, b, c\right\}$ слово $w=a^{n}(b c)^{n} a^{n}$ может быть использовано, чтобы опровергнуть автоматность $L$ с помощью леммы о разрастании, если предположить, что $n$ — это константа из леммы?

Доказать, что следующие языки в алфавите $\Sigma =\left\{ a, b, c\right\}$ не являются автоматными:

ДНФ записываются с использованием алфавита $\Sigma =\left\{ \wedge , \vee , \neg , a\right\}$, переменная $x_{i}$ обозначается повторением $i$ раз буквы $a$, например, $x_{1} \wedge \neg x_{2} \vee x_{3} \wedge x_{2}$ выглядит так: $a \wedge \neg a a \vee a a a \wedge a a$. Определить, будет ли автоматным язык:

Пусть $\boldsymbol {V}$ — это конечное множество переменных, $\boldsymbol {L}=\left\{ «(», \ll )>,<\lambda >\right\}$. Тогда $\lambda$-выражение — это слово в алфавите $\boldsymbol {V} \cup \boldsymbol {L}$, определяемое индуктивно: либо переменная $x \in \boldsymbol {V}$, либо « $\lambda x e_{1}$ », либо « $\left(e_{1} e_{2}\right) »$, где $x \in \boldsymbol {V}, e_{1}, e_{2}$ - $\lambda$-выражения. Например, слова « $\lambda x x$ », « $\lambda x(x x)$ », « $\lambda x \lambda x(\lambda x(x x) \lambda x(x x))$ » — это $\lambda$-выражения, а слова « $(x \lambda x) »$, « $\lambda x(\lambda x) »$ и « $\lambda x((x x) » \lambda$-выражениями не являются. Доказать, что множество $\lambda$-выражений в алфавите $\boldsymbol {V} \cup \boldsymbol {L}$ не является автоматным. $\circledast$

Выше в задаче 445 на стр. 132 строился автомат, который проверял правильность сложения двоичных чисел. Доказать, что для операции умножения двоичных чисел такого автомата не существует. Точнее, следующий язык в алфавите трёхэтажных символов не является автоматным: $\circledast$

Пусть $f$ — это некоторая $m$-местная функция на множестве натуральных чисел. Предположим, что существует конечный автомат, который проверяет корректность $f$ по аналогии с задачами 445 на стр. 132 и 522 на предыдущей странице. Это означает, что на вход этому автомату подаются $(m+1)$-этажные символы, на верхних этажах записаны в двоичном виде аргументы, на нижнем — предполагаемый результат. Доказать, что тогда существует константа $k$, для которой имеет место оценка $f\left(x_{1}, \ldots , x_{m}\right) \leqslant k \max \left\{ x_{1}, \ldots , x_{m}\right\}$ для произвольных натуральных чисел $x_{1}, \ldots , x_{m}$. $\circledast$

Пусть $f$ — некоторая одноместная функция на натуральных числах, которая монотонно не убывает. Предположим, что существует конечный автомат, который проверяет корректность $f$ по аналогии с задачей 523. Доказать что либо функция $f$ ограничена, либо существует константа $k>0$, для которой выполнена оценка $f(x) \geqslant k x$ для любого $x$. $\circledast$

Доказать, что условие монотонного неубывания функции $f$ в задаче 524 является существенным. Если его исключить, то утверждение может быть неверным. $\circledast$

Доказать, что следующий язык в алфавите $\Sigma =\left\{ a, b, c\right\}$ не является автоматным: $\circledast$

Используя лемму о разрастании, установить, какие из следующих языков в алфавите $\left\{ a, b\right\}$ не являются автоматными.

Пусть $C$ — схема кодирования из алфавита $\Sigma$ в себя. Привести пример, показывающий, что следующий язык может не быть автоматным:

то есть $L$ — множество слов, которые при кодировании могут переходить в себя же. $\circledast$

Операция коммутативного замыкания COMM заключается в произвольной перестановке букв слов языка:

Верно ли такое утверждение: если язык $L$ автоматный, то и язык $\operatorname {COMM}(L)$ тоже автоматный? $\circledast$

Доказать, что для односимвольного алфавита лемма о разрастании является не только необходимым, но и достаточным признаком автоматного языка: если указанная в лемме константа $n$ для языка $L$ существует, то язык $L$ автоматный. Указание. Рассмотреть слова короче $n$ и все остальные, последние разбить на классы в соответствием с остатком от деления длины слова на $n!$. $\circledast$

Пусть $C: \Sigma^{*} \rightarrow \Omega^{*}$ — гомоморфизм языков. Доказать, что проверка корректности $\varphi$ при помощи конечного автомата (по аналогии с задачами 523 и 524 на предшествующей странице) возможна тогда и только тогда, когда имеет место один из двух следующих случаев:

Доказать, что для любого натурального числа $n$ существует язык $L_{n}$, который может быть распознан (не)детерминированным конечным автоматом с $n+1$ состоянием, но не может быть распознан никаким автоматом с $n$ состояниями. $\circledast$

Пусть $k$ — мощность алфавита. Доказать, что для любого натурального числа $n$ недетерминированный конечный автомат с $n$ состояниями не может распознавать никакой конечный язык, содержащий больше чем

Доказать аналог леммы о разрастании для конечных преобразователей. Пусть $f: \Sigma^{*} \rightarrow \Omega^{*}$ — функция, вычисляемая некоторым конечным преобразователем $\mathfrak {M}$. Тогда существуют константы $n$ и $m$ такие, что для любого слова $w \in \Sigma^{*}$ и любого его фрагмента $u$ длины $n$ или более: $w=\alpha u \beta ,\left|u\right| \geqslant n$, выполнено следующее. Существует разбиение $u=x y z, 1 \leqslant \left|y\right| \leqslant n$, и разбиение $f(w)=X Y Z \in \Omega^{*}$ такие, что $f\left(\alpha x y^{i} z \beta \right)=X Y^{i} Z$ для всех натуральных $i,\left|X\right| \leqslant m\left|\alpha x\right|$, $\left|Y\right| \leqslant m\left|y\right|$ и $\left|Z\right| \leqslant m\left|z \beta \right|$. $\circledast$

Пользуясь задачей 534, показать, что не существует конечных преобразователей, которые выполняли бы перевод числа из унарной записи в двоичную и наоборот (см. раздел 24). $\circledast$

Пользуясь задачей 534, показать, что не существует конечных преобразователей, которые выполняли бы «переворачивание» слова в алфавите $\left\{ a, b\right\}$. $\circledast$

Найти разнозначный гомоморфизм $C: \Sigma^{*} \rightarrow \Omega^{*}$, который вычисляется некоторым конечным преобразователем, но обратное к $C$ кодирование $C^{-1}$ никаким конечным преобразователем выполнено быть не может. Считаем, что $C^{-1}(w)$ может быть любым, если $w \notin \operatorname {rng} C$. $\circledast$