Недетерминированный автомат

Определение недетерминированного автомата

Автомат называется недетерминированный, если его функция перехода неоднозначна.

Если язык описан недетерминированным автоматом, то возникает проблема неоднозначности описания. Эта проблема решается с помощью следующей теоремы:

Теорема: По каждому недетерминированному автомату, допускающему язык L, можно построить детерминированный автомат, допускающий тот же язык.

Пример: A= (Z, X, t, z₀, F),

Z - множество состояний = {z₀, z₁, z₂, z_F}

X= {0, 1}

F= {z_F}

Этот автомат - недетерминированный. В детерминированном автомате нет выходящих дуг с одинаковыми символами.

6.2