Конечные автоматы удобно задавать таблицей или диаграммой переходов. (с81)

Рис.4 Диаграмма переходов КА

Конечные автоматы подразделяются на детерминированные и недетерминированные. (c 82)

До этого мы рассматривали детерминированные конечные автоматы.

Детерминированным конечным автоматом (ДКА) называется такой автомат, в котором для каждой последовательности входных символов существует лишь одно состояние, в которое автомат может перейти из текущего.

Недетерминированный конечный автомат (НКА) является обобщением детерминированного. Существенная разница между детерминированной и недетерминированной моделями конечного автомата состоит в том, что значение g(q_i, a_j) является (возможно пустым) множеством состояний, а не одним состоянием.

Запись g(q_i, a_j) = {p1, p2,..., pk} Є Q означает, что недетерминированный конечный автомат M в состоянии q_i, сканируя символ a_j на входной ленте, продвигает входную головку вправо к следующей ячейке и выбирает любое из состояний p1, p2,..., pk в качестве следующего.

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

Пусть L — множество, принимаемое недетерминированным конечным автоматом. Тогда существует детерминированный конечный автомат, который принимает L.

Однако, поскольку количество состояний в эквивалентном ДКА в худшем случае растёт экспоненциально с ростом количества состояний исходного НКА, на практике подобная детерминизация не всегда возможна.

В силу последнего замечания, несмотря на бо́льшую сложность недетерминированных конечных автоматов, для задач, связанных с обработкой текста, преимущественно применяются именно НКА.

Примеры: (с 83)

Допустим, на вход НКА поступила цепочка «100100».