Понятие об автоматах, их задание графами

2325
0
08 июля 2009
(38.4.) Сформулируем понятие конечного автомата, обозначим входной алфавит, выходной алфавит, алфавит состояний, функцию переходов, функцию выходов, на рисунке изобразим граф переходов.

Теория автоматов, т.е. устройств со входами и выходами, имеет отношение к ее приложениям в создании цифровых устройств.

О: В качестве конечного автомата понимают систему38.4_html_m44d03a8c.gif, которая подразумевает, что38.4_html_m3f8a658.gifявляется входным алфавитом,38.4_html_58afa86b.gif- выходным алфавитом,38.4_html_m5d43c100.gif- алфавит состояний,38.4_html_m59e27590.gifесть функция переходов,38.4_html_m70aaf61e.gifпредставляет собой функцию выходов.

В силу того, что функции38.4_html_3d151ac8.gifопределены на конечных множествах, иными словами, являются дискретными, они могут быть заданы таблицами. Как правило две таблицы сводят в одну. Составленная в результате таблица именуются таблицей переходов автомата, ее также называют автономной таблицей.

Обозначим таблицу переходов автомата с38.4_html_m5002c630.gif

38.4_html_5204ac79.gifв следующем виде:

 

(38.1)

 

 

38.4_html_m3df73ac4.gif

38.4_html_m1aba9ed1.gif

38.4_html_mda89640.gif

38.4_html_m7f458128.gif

38.4_html_m2636635c.gif

38.4_html_272b6357.gif

38.4_html_f4bcb17.gif

38.4_html_m3e329a34.gif

38.4_html_m4a7480a9.gif

38.4_html_5fe6ef6a.gif

38.4_html_m765893c3.gif

38.4_html_320fbf55.gif

38.4_html_m747b7130.gif

38.4_html_5df8040c.gif

38.4_html_me6bc291.gif

38.4_html_6b86ff9c.gif

38.4_html_445dd92.gif

38.4_html_m747b7130.gif

38.4_html_m631f3d8b.gif

 

 

Ориентированный мультиграф (граф переходов, диаграмма переходов) представляет собой наглядный способ задания автомата. Для вершин графа характерно соответствие состояний: при38.4_html_11fb6f88.gifиз38.4_html_m30d64118.gifв38.4_html_m58c77976.gifведет ребро, которое имеет обозначение38.4_html_2dcab722.gif

На рис. 38.16 представлен граф переходов для таблицы (38.1).

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

 38.4_html_m25325f05.gif
Рис. 38. 16

 



(38.3.) Большинство графов, которые используются в приложениях (например, графы сортировок, классификаций) предполагают наличие диаграмм, именуемых деревьями. Связный неориентированный граф без циклов, в частности, предполагающий отсутствие петель и кратных ребер, именуют деревом. Несвязный неориентированный граф без цикла — лес, его связные компоненты являются деревьями.
6893 0
(38.2.) В рамках обозначенной темы рассмотрим случай определения связного неориентированного мультиграфа в качестве эйлерова и гамильтонова графа.
8704 0
(38.1.) Одним из базовых разделов дискретной математики можно назвать теорию графов. Их применяют при решении задач теории автоматического управления. Применение их актуально и в таких науках, где существуют системы с большим количеством объектов, которые предполагают взаимосвязь, определяемую разнообразными отношениями.
4503 0

    Вы должны авторизоваться, чтобы оставлять комментарии.

    Радиомастер
    © 2005–2013 radiomaster.ru
    admin@radiomaster.ru
    При использовании материалов данного сайта прямая и явная ссылка на сайт radiomaster.ru обязательна. 0.3174 s