ДИАГРАММЫ ПЕРЕХОДОВ

Пусть Â = (A, B, Q, j, y) - это автомат и
A= {a1, . . . , am}, Q= {q1, . . . , qr}.

Изобразим состояния Â с помощью системы из r непересекающихся кругов на плоскости, которые помечены символами этих состояний. Из каждого круга, изображающего состояние, проведем m ориентированных дуг, каждая из которых помечена одним из символов входного алфавита.

Дуге, выходящей из состояния qj, помеченной входным символомai, припишем также выходной символ y(ai,qj), заключив его в скобки.

Проведем эту дугу в состояние j(ai,qj).

Соответствующий фрагмент изображения автомата имеет вид, приведенный на рис.7.1.

qj qk

ai(y(ai,qj))

Рис. 7.1

Здесь qk = j(ai,qj).

Построенное по заданным правилам представление автомата называется диаграммой переходов.

Диаграммы переходов полностью определяют представляемые ими автоматы.

Множества A и B определяются символами, приписанными дугам без скобок и в скобках соответственно.

(Без ограничения общности можно считать, что каждый символ выходного алфавита принадлежит области значений функции выхода y и поэтому присутствует на диаграмме переходов.)

Множество всех состояний автомата Âзадается помеченными кругами.

Отображения j и y полностью представлены в диаграмме. При этом значение j(ai,qj) равно состоянию, в которое ведет дуга диаграммы, выходящая из состояния qj и помеченная входным символом ai.

Значение y(ai,qj) равно символу выходного алфавита, который приписан в скобках для той же дуги.

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

Если в некоторый момент времени tавтомат Âнаходится в состоянии qj и на его вход поступает символ ai, то функционирование этого автомата можно представить с помощью перемещения по диаграмме из состояния qj по дуге, помеченной входным символом ai.

При этом выбранная дуга ведет в состояние, в котором Â будет находиться в момент времени t + 1. Символ на выходе автомата в момент t приписан этой же дуге в скобках.

Поэтому функционирование автомата Â в последовательные моменты t0, t0+1, . . . ,t0+i,. . . можно промоделировать с помощью прохождения соответствующего пути в диаграмме переходов.

Упражнение. Покажите, что диаграмма переходов всякого автомата имеет элементарные циклы ненулевой длины.

 








Дата добавления: 2015-09-18; просмотров: 585;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.006 сек.