Избранные главы дискретной математики (стр. 7 из 7)

Третьим разделом теории конечных автоматов является теория вероятностных автоматов и самоорганизующихся систем.

Основные приложения теория конечных автоматов имеет в практике проектирования и автоматизации проектирования дискретных устройств и, в частности, вычислительных машин. Она приобретает всё более важное значение для таких классических математических дисциплин, как теория алгоритмов, с одной стороны, и таких современных теорий в математике и кибернетике, как теория формальных систем, теория программирования, теория формальных языков и грамматик — с другой.

По способу формирования функций выходов выделяют автоматы Мили и Мура.

Автомат Мили

В автомате Мили функция выходов λ определяет значение выходного символа по классической схеме абстрактного автомата. Математическая модель автомата Мили и схема рекуррентных соотношений не отличаются от математической модели и схемы рекуррентных соотношений абстрактного автомата. Таким образом, можно дать следующее определение:

Конечным детерминированным автоматом типа Мили называется совокупность пяти объектов

,

где S, X и Y — конечные непустые множества, а δ и λ — отображения вида:

со связью элементов множеств S, X и Y в абстрактном времени T = {0, 1, 2, …} уравнениями:

(Отображения δ и λ получили названия, соответственно функции переходов и функции выходов автомата A).

Особенностью автомата Мили является то, что функция выходов является двухаргументной и символ в выходном канале y(t) обнаруживается только при наличии символа во входном канале x(t). Функциональная схема не отличается от схемы абстрактного автомата.

Автомат Мура

Зависимость выходного сигнала только от состояния представлена в автоматах типа Мура. В автомате Мура функция выходов определяет значение выходного символа только по одному аргументу — состоянию автомата. Эту функцию называют также функцией меток, так как она каждому состоянию автомата ставит метку на выходе.

Функциональная схема автомата Мура

Конечным детерминированным автоматом типа Мура называется совокупность пяти объектов:

,

где S, X, Y и δ — соответствуют определению автомата типа Мили, а μ является отображением вида: μ : S → Y, с зависимостью состояний и выходных сигналов во времени уравнением:

Особенностью автомата Мура является то, что символ y(t) в выходном канале существует все время пока автомат находится в состоянии s(t).

Для любого автомата Мура существует автомат Мили, реализующий туже самую функцию. И наоборот: для любого автомата Мили существует соответствующий автомат Мура.

Функциональная схема автомата Мура

Список литературы:

1. Ru.wikipedia.org

2. http://chaos.ssu.runnet.ru

3. Столл Р. Р. Множества. Логика. Аксиоматические теории. — М.: Просвещение, 1968. — 232 с.

4. Intuit.ru

5. Уилсон Р. Введение в теорию графов. Пер с англ. М.: Мир, 1977. 208с.

6. http://www.citforum.ru/

7. Ерош И. Л. Дискретная математика. Комбинаторика — СПб.: СПбГУАП, 2001. — 37 c.

8. Риордан Дж. Введение в комбинаторный анализ. — пер. с англ.. — М.: 1963.