Эта лекция содержит дополнительные результаты, не используемые в дальнейшем изложении. В начале лекции доказывается замкнутость класса всех автоматных языков относительно взятия гомоморфного образа и относительно взятия полного гомоморфного прообраза.
В разделе 4.2* определяются понятия побуквенного гомоморфизма и локального языка и доказывается еще один критерий автоматности: среди языков, не содержащих пустого слова, автоматными являются в точности образы локальных языков при побуквенных гомоморфизмах.
В последнем разделе этой лекции устанавливается числовой критерий автоматности для языков над однобуквенным алфавитом (в терминах арифметических прогрессий) и доказывается связанное с длинами слов необходимое условие автоматности (для произвольного алфавита).
Теорема 4.1.1. Для любого гомоморфизма $$h \colon \Sigma_1^* \to \Sigma_2^*$$ и автоматного языка $$L \subseteq \Sigma_1^*$$ язык h(L) является автоматным.
Доказательство.
Пусть исходный язык L
задан конечным автоматом $$M = \langle Q , \Sigma_1 , \Delta , I , F \rangle$$.
Положим$$\Delta' = \{ \langle p , h ( x ) , q \rangle \mid
\langle p , x , q \rangle \in \Delta \} .$$
Тогда
язык h(L)
распознается конечным автоматом $$\langle Q , \Sigma_2 , \Delta' , I , F \rangle$$.
Теорема 4.1.2. Для любого гомоморфизма $$h \colon \Sigma_1^* \to \Sigma_2^*$$ и автоматного языка $$L \subseteq \Sigma_2^*$$
язык h-1(L) является автоматным.
Доказательство.
Без ограничения общности можно предположить,
что исходный язык L
задан конечным автоматом $$M = \langle Q , \Sigma_2 , \Delta , I , F \rangle$$,
где $$\Delta$$
не содержит переходов с метками длины больше единицы.
Положим$$\Delta' =
\{ \lp p , a , q \rp \mid
a \in \Sigma_1
\text{ и существует путь из } p \text{ в } q
\text{ с меткой } h ( a )
\} .$$
Язык h-1(L)
распознается конечным автоматом $$\langle Q , \Sigma_1 , \Delta' , I , F \rangle$$.
Упражнение 4.1.3. Существует ли такой
автоматный язык L
над алфавитом {a,b},
что язык $$\{ a^{|w|_b} \mid w \in L \}$$
не является автоматным?}
Упражнение 4.1.4. Существует ли такой
автоматный язык L
над алфавитом {a,b},
что язык $$\{ w \in \{a,b\}^* \mid a^{|w|_a} \in L \}$$
не является автоматным?}
Упражнение 4.1.5. Существует ли такой
автоматный язык L
над алфавитом {a,b},
что язык $$\{ w \in \{a,b\}^* \mid ( \exists x \in L )\, | x | = | w | \}$$
не является автоматным?
Определение 4.2.1.
Гомоморфизм $$h \colon \Sigma_1^* \to \Sigma_2^*$$
называется побуквенным (length-preserving),
если |h(a)| = 1
для каждого $$a \in \Sigma_1$$.
Замечание 4.2.2.
Гомоморфизм $$h \colon \Sigma_1^* \to \Sigma_2^*$$
является побуквенным
тогда и только тогда, когда |h(w)| = |w|
для каждого слова $$w \in \Sigma_1^*$$.
Определение 4.2.3. Язык $$L \subseteq \Sigma^*$$ называется локальным, если существуют такие языки $$L_1 \subseteq \Sigma^*$$, $$L_2 \subseteq \Sigma^*$$, $$L_3 \subseteq \Sigma^*$$, что
L1 и L2
содержат только однобуквенные слова;L3
содержит только двухбуквенные слова;Лемма 4.2.4. Каждый локальный язык является автоматным.
Очевидно, что языки L1, L2 и L3
в определении 4.2.3 являются конечными.
Остается применить
замечание 2.1.19 и теоремы 3.1.1 и 3.2.1
(напомним, что разность языков выражается через
пересечение и дополнение).
Теорема 4.2.5. Пусть L - язык над алфавитом $$\Sigma$$ и L не содержит пустого слова. Язык L является автоматным
тогда и только тогда, когда
существуют
такие
алфавит $$\Sigma_0$$, локальный язык $$L_0 \subseteq \Sigma_0^*$$ и побуквенный гомоморфизм $$h \colon \Sigma_0^* \to \Sigma^*$$,
что L = h(L0).
Доказательство. Достаточность следует из леммы 4.2.4 и теоремы 4.1.1.
Для доказательства необходимости
рассмотрим конечный автомат $$\langle Q , \Sigma , \Delta , I , F \rangle$$
с однобуквенными переходами,
задающий язык L.
В качестве алфавита $$\Sigma_0$$
возьмем множество $$\Delta$$.
Положим$$\begin{align*}
L_1 = \{ \lp p , a , q \rp \mid
\lp p , a , q \rp \in \Delta \commaand p \in I \} ,\\
L_2 = \{ \lp p , a , q \rp \mid
\lp p , a , q \rp \in \Delta \commaand q \in F \} ,\\
L_3 =
\{ \lp p_1 \!, a_1 \!, q_1 \rp \lp p_2 , a_2 , q_2 \rp \mid
\lp p_1 \!, a_1 \!, q_1 \rp \squeeze{\in} \Delta ,\
\lp p_2 , a_2 , q_2 \rp \squeeze{\in} \Delta
\commaand q_1 \squeeze{\neq} p_2 \}
\end{align*}$$
и $$h ( \lp p , a , q \rp ) = a$$
для каждого $$\lp p , a , q \rp \in \Delta$$.
Пример 4.2.6.
Пусть $$\Sigma \peq \{ a , b , c \}$$.
Рассмотрим конечный автомат M2
из примера 3.1.3
и обозначим L = L(M2).
Применим конструкцию из доказательства
теоремы 4.2.5
к языку L.
Для удобства заменим $$\lp 4 , c , 4 \rp$$
на d, $$\lp 4 , a , 5 \rp$$
на e
и $$\lp 5 , c , 5 \rp$$
на f.
Получим алфавит $$\Sigma_0 \peq \{ d , e , f \}$$
и локальный язык$$L_0 = ( ( \{ d , e \} \cdot \Sigma_0^* ) \cap
( \Sigma_0^* \cdot \{ e , f \} ) ) \sminus
( \Sigma_0^* \cdot \{ df , ed , ee , fd , fe \} \cdot \Sigma_0^* ) .$$
Можно доказать, что$$L_0 = \{ d^m e f^n \mid m \geq 0 ,\ n \geq 0 \} .$$
Побуквенный гомоморфизм h
задается равенствами $$h(d) = c$$, $$h(e) = a$$
и $$h(f) = c$$.
Легко проверить, что действительно L = h(L0).
Упражнение 4.2.7. Пусть $$\Sigma = \{a,b,c,d\}$$.
Существует ли такой побуквенный гомоморфизм $$h \colon \Sigma^* \farrow \Sigma^*$$,
что h(abc) = bac
и h(da) = da?}
Упражнение 4.2.8. Является ли локальным язык$$\{ (ab)^n \mid n \geq 1 \}$$ над алфавитом $$\Sigma = \{a,b\}$$?
Упражнение 4.2.9. Является ли локальным язык$$\{ aa u \mid u \in \{a,b\}^* \}$$ над алфавитом $$\Sigma = \{a,b\}$$?
Упражнение 4.2.10. Является ли локальным язык$$\{ b u a \mid u \in \{a,b,c\}^* \}$$ над алфавитом $$\Sigma = \{a,b,c\}$$?
Определение 4.3.1.
Пусть $$\cala \subseteq \mathbb{N}$$, $$m \in \mathbb{N}$$
и $$m > 0$$.
Множество $$\cala$$
называется заключительно периодическим
(m,
если выполнено условие$$( \exists n_0 \in \mathbb{N} ) \, ( \forall n \geq n_0 ) \,
( n \in \cala \liff n + m \in \cala ) .$$
Лемма 4.3.2. Пусть $$\cala \subseteq \mathbb{N}$$. Тогда равносильны следующие утверждения:
m и конечные множества $$\calm \subseteq \mathbb{N}$$ и $$\calk \subseteq \{ 0 , 1 , \ldots , m - 1 \}$$, что$$\cala =
\{ k \in \mathbb{N} \mid ( k \mybmod m ) \in \calk \} \sminus \calm ;$$
Теорема 4.3.3. Язык L над однобуквенным алфавитом {a} является автоматным
тогда и только тогда, когда
множество $$\{ k \in \mathbb{N} \mid a^k \in L \}$$ является заключительно периодическим.
Доказательство.
Для доказательства необходимости достаточно рассмотреть
детерминированный конечный автомат, распознающий язык L.
Теорема 4.3.4. Если язык L является автоматным, то множество $$\{ | w | \mid w \in L \}$$ является заключительно периодическим.
Доказательство.
Рассмотрим конечный автомат, распознающий язык L.
Заменим все символы в метках переходов на символ a.
Осталось применить теорему 4.3.3
к полученному автоматному языку над однобуквенным алфавитом {a}.
Упражнение 4.3.5.
Существует ли такой автоматный язык L
над алфавитом {a},
что язык $$\{ a^n \mid a^{n^2} \in L \}$$
не является автоматным?
Упражнение 4.3.6.
Существует ли такой автоматный язык L
над алфавитом {a},
что язык $$\{ a^n \mid a^{2^n} \in L \}$$
не является автоматным?
Упражнение 4.3.7.
Существует ли такой автоматный язык L1
над алфавитом $$\Sigma$$,
что язык$$L_2 \peq \{ w \in \Sigma ^* \mid w x \in L_1 \commaand | x | = 2^{ | w | }
\mathspace\text{для некоторого слова}\mathspace
x \squeeze{\in} \Sigma ^* \}$$
не является автоматным?
Упражнение 4.3.8.
Существует ли такой
автоматный язык L
над алфавитом {a,b},
что язык $$\{ a^{2^n} \mid a^n \notin L \}$$
не является автоматным?
Упражнение 4.3.9.
Существует ли такой
автоматный язык L
над алфавитом {a,b},
что язык $$\{ a^n \mid a^{n^3} \notin L \}$$
не является автоматным?
Эта лекция содержит дополнительные результаты, не используемые в дальнейшем изложении. В начале лекции доказывается замкнутость класса всех автоматных языков относительно взятия гомоморфного образа и относительно взятия полного гомоморфного прообраза.
В разделе 4.2* определяются понятия побуквенного гомоморфизма и локального языка и доказывается еще один критерий автоматности: среди языков, не содержащих пустого слова, автоматными являются в точности образы локальных языков при побуквенных гомоморфизмах.
В последнем разделе этой лекции устанавливается числовой критерий автоматности для языков над однобуквенным алфавитом (в терминах арифметических прогрессий) и доказывается связанное с длинами слов необходимое условие автоматности (для произвольного алфавита).
Теорема 4.1.1. Для любого гомоморфизма $$h \colon \Sigma_1^* \to \Sigma_2^*$$ и автоматного языка $$L \subseteq \Sigma_1^*$$ язык h(L) является автоматным.
Доказательство.
Пусть исходный язык L
задан конечным автоматом $$M = \langle Q , \Sigma_1 , \Delta , I , F \rangle$$.
Положим$$\Delta' = \{ \langle p , h ( x ) , q \rangle \mid
\langle p , x , q \rangle \in \Delta \} .$$
Тогда
язык h(L)
распознается конечным автоматом $$\langle Q , \Sigma_2 , \Delta' , I , F \rangle$$.
Теорема 4.1.2. Для любого гомоморфизма $$h \colon \Sigma_1^* \to \Sigma_2^*$$ и автоматного языка $$L \subseteq \Sigma_2^*$$
язык h-1(L) является автоматным.
Доказательство.
Без ограничения общности можно предположить,
что исходный язык L
задан конечным автоматом $$M = \langle Q , \Sigma_2 , \Delta , I , F \rangle$$,
где $$\Delta$$
не содержит переходов с метками длины больше единицы.
Положим$$\Delta' =
\{ \lp p , a , q \rp \mid
a \in \Sigma_1
\text{ и существует путь из } p \text{ в } q
\text{ с меткой } h ( a )
\} .$$
Язык h-1(L)
распознается конечным автоматом $$\langle Q , \Sigma_1 , \Delta' , I , F \rangle$$.
Упражнение 4.1.3. Существует ли такой
автоматный язык L
над алфавитом {a,b},
что язык $$\{ a^{|w|_b} \mid w \in L \}$$
не является автоматным?}
Упражнение 4.1.4. Существует ли такой
автоматный язык L
над алфавитом {a,b},
что язык $$\{ w \in \{a,b\}^* \mid a^{|w|_a} \in L \}$$
не является автоматным?}
Упражнение 4.1.5. Существует ли такой
автоматный язык L
над алфавитом {a,b},
что язык $$\{ w \in \{a,b\}^* \mid ( \exists x \in L )\, | x | = | w | \}$$
не является автоматным?
Определение 4.2.1.
Гомоморфизм $$h \colon \Sigma_1^* \to \Sigma_2^*$$
называется побуквенным (length-preserving),
если |h(a)| = 1
для каждого $$a \in \Sigma_1$$.
Замечание 4.2.2.
Гомоморфизм $$h \colon \Sigma_1^* \to \Sigma_2^*$$
является побуквенным
тогда и только тогда, когда |h(w)| = |w|
для каждого слова $$w \in \Sigma_1^*$$.
Определение 4.2.3. Язык $$L \subseteq \Sigma^*$$ называется локальным, если существуют такие языки $$L_1 \subseteq \Sigma^*$$, $$L_2 \subseteq \Sigma^*$$, $$L_3 \subseteq \Sigma^*$$, что
L1 и L2
содержат только однобуквенные слова;L3
содержит только двухбуквенные слова;Лемма 4.2.4. Каждый локальный язык является автоматным.
Очевидно, что языки L1, L2 и L3
в определении 4.2.3 являются конечными.
Остается применить
замечание 2.1.19 и теоремы 3.1.1 и 3.2.1
(напомним, что разность языков выражается через
пересечение и дополнение).
Теорема 4.2.5. Пусть L - язык над алфавитом $$\Sigma$$ и L не содержит пустого слова. Язык L является автоматным
тогда и только тогда, когда
существуют
такие
алфавит $$\Sigma_0$$, локальный язык $$L_0 \subseteq \Sigma_0^*$$ и побуквенный гомоморфизм $$h \colon \Sigma_0^* \to \Sigma^*$$,
что L = h(L0).
Доказательство. Достаточность следует из леммы 4.2.4 и теоремы 4.1.1.
Для доказательства необходимости
рассмотрим конечный автомат $$\langle Q , \Sigma , \Delta , I , F \rangle$$
с однобуквенными переходами,
задающий язык L.
В качестве алфавита $$\Sigma_0$$
возьмем множество $$\Delta$$.
Положим$$\begin{align*}
L_1 = \{ \lp p , a , q \rp \mid
\lp p , a , q \rp \in \Delta \commaand p \in I \} ,\\
L_2 = \{ \lp p , a , q \rp \mid
\lp p , a , q \rp \in \Delta \commaand q \in F \} ,\\
L_3 =
\{ \lp p_1 \!, a_1 \!, q_1 \rp \lp p_2 , a_2 , q_2 \rp \mid
\lp p_1 \!, a_1 \!, q_1 \rp \squeeze{\in} \Delta ,\
\lp p_2 , a_2 , q_2 \rp \squeeze{\in} \Delta
\commaand q_1 \squeeze{\neq} p_2 \}
\end{align*}$$
и $$h ( \lp p , a , q \rp ) = a$$
для каждого $$\lp p , a , q \rp \in \Delta$$.
Пример 4.2.6.
Пусть $$\Sigma \peq \{ a , b , c \}$$.
Рассмотрим конечный автомат M2
из примера 3.1.3
и обозначим L = L(M2).
Применим конструкцию из доказательства
теоремы 4.2.5
к языку L.
Для удобства заменим $$\lp 4 , c , 4 \rp$$
на d, $$\lp 4 , a , 5 \rp$$
на e
и $$\lp 5 , c , 5 \rp$$
на f.
Получим алфавит $$\Sigma_0 \peq \{ d , e , f \}$$
и локальный язык$$L_0 = ( ( \{ d , e \} \cdot \Sigma_0^* ) \cap
( \Sigma_0^* \cdot \{ e , f \} ) ) \sminus
( \Sigma_0^* \cdot \{ df , ed , ee , fd , fe \} \cdot \Sigma_0^* ) .$$
Можно доказать, что$$L_0 = \{ d^m e f^n \mid m \geq 0 ,\ n \geq 0 \} .$$
Побуквенный гомоморфизм h
задается равенствами $$h(d) = c$$, $$h(e) = a$$
и $$h(f) = c$$.
Легко проверить, что действительно L = h(L0).
Упражнение 4.2.7. Пусть $$\Sigma = \{a,b,c,d\}$$.
Существует ли такой побуквенный гомоморфизм $$h \colon \Sigma^* \farrow \Sigma^*$$,
что h(abc) = bac
и h(da) = da?}
Упражнение 4.2.8. Является ли локальным язык$$\{ (ab)^n \mid n \geq 1 \}$$ над алфавитом $$\Sigma = \{a,b\}$$?
Упражнение 4.2.9. Является ли локальным язык$$\{ aa u \mid u \in \{a,b\}^* \}$$ над алфавитом $$\Sigma = \{a,b\}$$?
Упражнение 4.2.10. Является ли локальным язык$$\{ b u a \mid u \in \{a,b,c\}^* \}$$ над алфавитом $$\Sigma = \{a,b,c\}$$?
Определение 4.3.1.
Пусть $$\cala \subseteq \mathbb{N}$$, $$m \in \mathbb{N}$$
и $$m > 0$$.
Множество $$\cala$$
называется заключительно периодическим
(m,
если выполнено условие$$( \exists n_0 \in \mathbb{N} ) \, ( \forall n \geq n_0 ) \,
( n \in \cala \liff n + m \in \cala ) .$$
Лемма 4.3.2. Пусть $$\cala \subseteq \mathbb{N}$$. Тогда равносильны следующие утверждения:
m и конечные множества $$\calm \subseteq \mathbb{N}$$ и $$\calk \subseteq \{ 0 , 1 , \ldots , m - 1 \}$$, что$$\cala =
\{ k \in \mathbb{N} \mid ( k \mybmod m ) \in \calk \} \sminus \calm ;$$
Теорема 4.3.3. Язык L над однобуквенным алфавитом {a} является автоматным
тогда и только тогда, когда
множество $$\{ k \in \mathbb{N} \mid a^k \in L \}$$ является заключительно периодическим.
Доказательство.
Для доказательства необходимости достаточно рассмотреть
детерминированный конечный автомат, распознающий язык L.
Теорема 4.3.4. Если язык L является автоматным, то множество $$\{ | w | \mid w \in L \}$$ является заключительно периодическим.
Доказательство.
Рассмотрим конечный автомат, распознающий язык L.
Заменим все символы в метках переходов на символ a.
Осталось применить теорему 4.3.3
к полученному автоматному языку над однобуквенным алфавитом {a}.
Упражнение 4.3.5.
Существует ли такой автоматный язык L
над алфавитом {a},
что язык $$\{ a^n \mid a^{n^2} \in L \}$$
не является автоматным?
Упражнение 4.3.6.
Существует ли такой автоматный язык L
над алфавитом {a},
что язык $$\{ a^n \mid a^{2^n} \in L \}$$
не является автоматным?
Упражнение 4.3.7.
Существует ли такой автоматный язык L1
над алфавитом $$\Sigma$$,
что язык$$L_2 \peq \{ w \in \Sigma ^* \mid w x \in L_1 \commaand | x | = 2^{ | w | }
\mathspace\text{для некоторого слова}\mathspace
x \squeeze{\in} \Sigma ^* \}$$
не является автоматным?
Упражнение 4.3.8.
Существует ли такой
автоматный язык L
над алфавитом {a,b},
что язык $$\{ a^{2^n} \mid a^n \notin L \}$$
не является автоматным?
Упражнение 4.3.9.
Существует ли такой
автоматный язык L
над алфавитом {a,b},
что язык $$\{ a^n \mid a^{n^3} \notin L \}$$
не является автоматным?
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.