2.2. Таблица переходов

Характеристические функции определяемые уравнениями (1.5) и (1.6), могут быть представлены в форме таблицы, известной под названием таблицы переходов. Таблица содержит перечень значений этих функций для всех возможных аргументов, т. е. для всех возможных упорядоченных пар , где принадлежит входному алфавиту X, — множеству состояний . Образец таблицы переходов для автомата с входным алфавитом выходным алфавитом и множеством состояний представлен таблицей 2.1. Таблица состоит из двух соседних подтаблиц -подтаблицы и -подтаблицы, которые определяют функции

Таблица 2.1. Общая таблица переходов (см. скан)

соответственно. Эти подтаблицы имеют общий основной столбец (левый крайний столбец), в котором перечислены все возможные состояния в настоящий момент столбцы в обеих подтаблицах озаглавлены одинаково, причем каждому возможному значению входного символа в настоящий момент соответствует в каждой подтаблице свой столбец. Таким образом, строки обозначены символами , а столбцы символами В клетке на пересечении строки и столбца в подтаблице z помещается значение (это значение будем называть значением ), а в подтаблице помещается значение значение будем называть значением Символы, записанные в клетках подтаблиц принадлежат выходному алфавиту Z и множеству состояний S соответственно или подмножествам этих множеств. Если — характеристические функции детерминированного полностью определенного автомата, то эти функции должны быть однозначно определены для каждой упорядоченной пары где принадлежит множеству — множеству S. Следовательно, подтаблица должна содержать в каждой клетке

точно один элемент из Z, а подтаблица точно один элемент из S.

Хотя описательные обозначения состояний (выбираемые так, как в примерах § 1.7) являются полезными для интуитивного понимания роли различных состояний при определении соотношений вход — выход и для определения функций по словесному описанию системы, они становятся бесполезными после того, как эти функции определены. Поэтому в таблице переходов первоначальные обозначения можно заменить любыми другими, удобными для исследователя. В большинстве примеров, приводимых в книге, состояния будут обозначаться просто цифрами 1, 2, 3 и т. д.

Для иллюстрации построения таблицы переходов приведена таблица 2.2, которая представляет собой таблицу переходов системы, описанной в примере 2 § 1.7. Эта система названа автоматом , а состояния «новое слово», «ждать нового слова», «появление и», «появление и «появление обозначены цифрами 1, 2, 3, 4 и 5 соответственно. Содержимое клеток таблицы представляет собой числовое отражение словесных доводов, объясняющих

Таблица 2.2. Автомат

выбор множества состояний в примере 2. Сравнение словесного описания с таблицей переходов позволяет оценить точность и краткость последней по сравнению с первым способом описания.