Теорема Клини. Для каждого КНА можно построить конечный детерминированный автомат (КДА), допускающий то же язык.
Алгоритм построения КДА для заданного КНА.
- Строим множество 2k-1 состояний, где k – количество состояний заданного автомата, причем каждое состояние соответствует одному элементу множества всех подмножеств состояний данного автомата (без пустого).
- Из каждого состояния S нового автомата направим дугу (не более одной) помеченную входным символом в такое состояние, которое соответствует множеству состояний заданного автомата, в которое есть дуги, помеченные этим символом хотя бы из одного состояния заданного автомата, образующего S.
- В качестве начального отметим состояние, соответствующее начальному состоянию заданного автомата.
- Как конечное пометим все состояния, в которые входят хотя бы одно из конечных состояний заданного автомата.
Полученный таким образом автомат является детерминированным и принимает тот же язык, что и заданный недетерминированный автомат. Недостижимые состояния автомата отбрасываются.
