Задать вопрос юристу

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

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

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

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

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

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

при

при

при

при

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

т.е.

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

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

Определить:

Решение.

поэтому

поэтому

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

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

поэтому


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

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

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

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

г)

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

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

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

б) 0020.

<< | >>
Источник: Дискретная математика. Лекции. 2016

Еще по теме §3.3. Продолжение функций и:

  1. Некоторые основные элементарные функции (продолжение)
  2. Глава четвертая. Последующие издания Свода законов гражданских в 1842 и 1857 гг.; продолжения к Своду законов и вопрос о продолжениях к своду вообще
  3. Аналитическое продолжение
  4. Функции журналистики. Понятие функцию Многообразие социальных и информационных потребностей общества – объективная основа функций журналистики.
  5. VIII (Дальнейшие исправления С. З. по второму продолжению)
  6. ПРЕДЛОЖЕНИЯ ОКХ ПО ПРОДОЛЖЕНИЮ ОПЕРАЦИЙ
  7. Продолжение министерских реформ
  8. "война есть продолжение политики"
  9.   6. Продолжение  
  10. 35 § 24. Продолжение
  11. Продолжение
  12. Продолжение
  13. Продолжения не последовало
  14. Иллюстрации (продолжение)
  15. Иллюстрации (продолжение)
  16. Иллюстрации (продолжение)
  17. Иллюстрации (продолжение)
  18. Иллюстрации (продолжение)