Задание автомата таблицей переходов больше подходит для программной реализации КА. Такая таблица имеет n=|N| строк, соответствующих всевозможным состояниям автомата, и k=|T| столбцов, соответствующих всевозможным входным сигналам автомата. В клетку таблицы в строке, соответствующей состоянию q, и в столбце, соответствующем входному сигналу a записывается содержимое d(q, a). Если в такой таблице выделить начальное состояние и заключительные состояния, то она будет однозначно определять весь автомат. Обычно также предусматривают дополнительно состояние E – состояние ошибки, которое переходит автомат, если функция переходов для данной пары «состояние-вход» не определена.
Рассмотрим таблицу переходов для автомата.
|
|
Вход |
|
|
состояние |
a |
b |
|
N |
B |
E |
|
B |
B |
B |
|
E |
E |
E |
Приведем алгоритм, реализующий универсальный распознаватель автоматных языков.
Пусть задано
тип tCondition [k]
