§3.3. Продолжение функций и

Пусть конечный алфавит. Обозначим через множество всех слов Число называется длиной слова и обозначается Например, если то Слово, в котором нет ни одной буквы, будем называть пустым словом и обозначать символом Очевидно, Пусть множество всех слов длины а множество всех непустых слов.

Произведением двух слов называется слово, полученное приписыванием к слову справа слова Таким образом, если то Нетрудно проверить, что произведение слов ассоциативно, т.е.

Произведение слов некоммутативно, так как в общем случае

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

Функции и можно продолжить до функций и следующим образом. Положим

при

при

при

при

Функция несёт информацию о том, в какое состояние перейдёт автомат, если на его вход будут поступать последовательно несколько букв из алфавита Действительно, если в какой-либо момент автомат находится в состоянии а на его вход поступают буквы то будут осуществляться следующие переходы в другие состояния:

т.е. в конце концов автомат окажется в состоянии Аналогичным образом интерпретируется функция А именно, где буква, которая будет выдана автоматом на -м шаге.

Пример 1. Автомат задан таблицей 3.5.

Определить:

Решение.

поэтому

поэтому

Пример 2. Автомат задан диаграммой Мура, изображенной на рис. 3.12. Найти: , .

Решение. Имеем:

поэтому

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

1. Автомат задан таблицей 3.6. Найти: а) б)

2.

Найти: а) б) в)

г)

3. Автомат задан каноническими уравнениями

где и вычисления производятся по модулю 3. Найти: а) , б) . Ответы:

1. а) б) 2. а) б) в) г) 3. а) 2;

б) 0020.