Детерминированность

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

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

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

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

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

Дата добавления: 2015-07-20