пользователей: 21277
предметов: 10471
вопросов: 178106
Конспект-online
зарегистрируйся или войди через vk.com чтобы оставить конспект.
РЕГИСТРАЦИЯ ЭКСКУРСИЯ


29. Теорема Клини. Алгоритм построения ДКА для заданного НКА.

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

Алгоритм построения КДА для заданного КНА.

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

Полученный таким образом автомат является детерминированным и принимает тот же язык, что и заданный недетерминированный автомат. Недостижимые состояния автомата отбрасываются.

 


19.01.2016; 06:42
хиты: 14
рейтинг:0
Точные науки
информатика
для добавления комментариев необходимо авторизироваться.
  Copyright © 2013-2016. All Rights Reserved. помощь