Задачи для самостоятельного решения

1. П остроить автомат с входным и выходным алфавитами и который отыскивает во входной последовательности идущие подряд более одного раза буквы и заменяет последнюю из них символом Символ _ зарезервирован здесь для начала последовательности. Пример:

Ответ см. на рис. 4.39.

1. П остроить диаграмму Мура автомата с который во входной последовательности заменяет символы, стоящие на чётных местах, на противоположные. Например,

Ответ см. на рис. 40.

2. Построить таблицу автомата с наименьшим числом состояний, удовлетворяющий условиям:

Ответ см. в таблице (ответ неоднозначен).

0	1	1	0	1
1	1	0	1	0

3. Автомат с работает по схеме, показанной на рисунке 4.41. При этом считается, что

а) Выразить через

б) Найти первые 3 символа в выходной последовательности, если

О тветы. а) б)

§ 4.5. Алгебраический подход к теории автоматов

Будем рассматривать автоматы без выхода, т.е. тройки где – функция переходов. Для упрощения записи применяем сокращённые обозначения, т.е. пишем вместо для При этом если пустое слово. Напомним, что множество является полугруппой, так как на этом множестве определено умножение и выполнен закон ассоциативности: Произведение элемента из на элемент из лежит в поэтому мы можем говорить о действии полугруппы на множестве А именно, если где то мы считаем, что элемент переводит в Действие полугруппы на множестве аналогично действию группы подстановок на множестве или действию скаляров на векторы в векторном пространстве.

Алгебраический подход к автоматам позволяет применять к ним методы абстрактной алгебры и пользоваться её понятиями, такими, как изоморфизм, гомоморфизм, подавтомат, фактор-автомат и т.д.

Автоматы и будем называть изоморфными и писать если существует взаимно однозначное отображение такое, что для всех Понятие изоморфизма можно расширить, распространив его на автоматы над разными алфавитами и в этом случае надо брать два взаимно однозначных отображения и

Гомоморфизм автоматов и над одним алфавитом – это отображение (не обязательно взаимно однозначное) такое, что для всех Понятие гомоморфизма может быть обобщено на автоматы над разными алфавитами.

Понятие подавтомата автомата обычно определяется одним из следующих способов:

а) подавтоматом является непустое подмножество такое, что

б) подавтомат – это тройка где непустое подмножество множества а непустое подмножество множества такие, что

Ясно, что определение б) является более общим, а при они совпадают.

Отношение эквивалентности на множестве называется конгруэнцией автомата если для всех Класс эквивалентности конгруэнции в котором лежит элемент обозначим Множество всех классов эквивалентности (фактор-множество) обозначим

Определим действие букв из на элементы множества полагая для Несложно проверяется корректность этого определения )т.е. независимость от выбора представителя в классе эквивалентности) и определяется отображение (очевидно, Автомат называется фактор-автоматом автомата по конгруэнции и обозначается В частности, приведённый автомат рассмотренный в п. 3.4, является фактор-автоматом автомата

Понятие автомата тесно связано (если не сказать “полностью совпадает” с понятием полигона над полугруппой. Пусть полугруппа и множество. Будем говорить, что полигон над если определено отображение удовлетворяющее условию при всех Всякий автомат можно рассматривать как полигон (а именно, полигон над полугруппой Наоборот, если полигон над полугруппой то можно рассматривать как автомат, причём превращение в автомат далеко не единственно. Один из способов (вообще говоря, неэкономный) состоит в том, что рассматривается как входной алфавит, а функция переходов.

Пусть абстрактный автомат (не обязательно конечный). Для каждого рассмотрим отображение определяемое по формуле Множество всех отображений где образуют полугруппу. Действительно, поэтому Полугруппа всех таких отображений называется полугруппой переходов автомата и обозначается Очевидно, множество состояний является полигоном над полугруппой

Упражнение 15. Доказать, что всякая полугруппа является полигоном над собой.

Доказательство. Умножение в полугруппе – это отображение Так как для всех то полигон над

Упражнение 16. Пусть группа и полигон над причём если а единица группы Орбитой элемента называется множество Доказать, что является объединением непересекающихся орбит.

Доказательство. Ясно, что является объединением орбит. Осталось доказать, что любые две орбиты либо не пересекаются, либо совпадают. Пусть Тогда для некоторых Отсюда Поэтому В силу симметрии Таким образом,

Упражнение 17. Что из себя представляет полугруппа переходов автомата, диаграмма которого изображена на рисунке 4.42?

Р ешение. Отображение действует так: поэтому можно записать Аналогично записываем Если пустое слово, то Перемножая всевозможными способами отображения между собой, получим полугруппу Многие произведения, конечно, совпадут. Например, и т.д. Различных оказывается 12 штук. Следовательно,

Упражнение 18. Пусть – группа, – её подгруппа, – множество всех правых смежных классов. Доказать, что является -полигоном относительно операции

Доказательство. Утверждение очевидно ввиду равенства