пользователей: 25142
предметов: 11218
вопросов: 199732
Конспект-online
РЕГИСТРАЦИЯ ЭКСКУРСИЯ


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

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

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

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

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

 


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