ГЛАВА 2. ТАБЛИЦЫ, ГРАФЫ И МАТРИЦЫ ПЕРЕХОДОВ

2.1. Введение

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