Выбор переходов

 

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

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

Рассмотрим два метода решения задачи выбора перехода для заданного входного символа.

1. Метод вектора переходов. Согласно этому метода, адреса или метки процедур переходов, на которые должно передаваться управление, хранятся в виде вектора в последовательных ячейках для каждого входного символа. Очередной входной символ служит индексом, по которому выбирается элемент вектора, дающий нужный переход.

Пример:

Таблица переходов конечного процессора:

								K
A	A1			B3		A6
B		C2	C3	A4		B6		C1
C					B5

 

Вектор для состояния А:

								K
A	A1					A6

 

В большинстве языков программирования этот метод реализуется использованием переключателя или вычисляемого перехода.

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

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

Пример:

Список переходов для состояния А:

	A1
	B3
	A6

Переход по неудаче – обработчик ошибки.

 

При поступлении нового входного символа происходит поиск этого символа и соответствующего ему перехода.

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

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

 

Замечания:

3. Если соответствие моделирующего автомата хранится в явном виде, то в это случае принципы указанных методов применимы, но возможны многочисленные варианты.

4. Можно пользоваться состояниями как индексом для передачи управления в одну из уже описанных процедур.

5. Можно хранить таблицу переходов как 2-мерный массив, индексы которого – состояния и входные символы.

6. Можно использовать метод списка для выбора элементов из столбцов, а не из строк таблицы переходов.

7. Разработчику рекомендуется самому выбирать метод в соответствии со своей конкретной задачей и особенностями ЭВМ.

 

Вопросы и упражнения

1. Составьте таблицу переходов данного автомата для цепочки 001101.

Опишите переходы методом вектора переходов и методом списка переходов. Каким из методов это удобнее сделать?