Интернет магазин китайских планшетных компьютеров

Компьютеры - Конечный автомат - Детерминированность

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

Детерминированный конечный автомат

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

• Недетерминированный конечный автомат является обобщением детерминированного. Недетерминированность автоматов достигается двумя способами:

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

Если рассмотреть случай, когда автомат задан следующим образом: , где:

• S — множество стартовых состояний автомата, такое что ;

Тогда появляется третий признак недетерминизма - наличие нескольких начальных состояний у автомата .

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

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