Преобразование NFA в DFA, язык которого является дополнением к L (A)

Question

Может кто-нибудь помочь мне с этим вопросом?

Опишите алгоритм, который преобразует NFA в DFA, язык которого является дополнением к L (A).Дополнение должно быть принято в отношении алфавита А. Учитывая неформальный аргумент, почему ваша конструкция работает.Вам не нужно давать формальное доказательство.

Любое руководство приветствуется ...

Answer 1

Вы можете преобразовать FA в его дополнение, превратив его принимающие состояния в неприемлемые состояния и превратив его непринятые состояния в принимающие состояния. Легко!

Вы можете преобразовать NFA в DFA, считая, что любое состояние NFA является степенью состояний: то есть для каждого состояния в NFA оно либо активно, либо не активно. Вы можете сопоставить каждое из этих состояний с состоянием в DFA, так что вы получите не более 2 ^{| Q |} состояний для вашего DFA, который представляет ваш NFA.

Редактировать: этот алгоритм и его доказательство на самом деле не нуждаются в деталях A, если он является действительным автоматом конечного состояния.