0

誰かがこの質問で私を助けてくれますか?

NFA を言語が L(A) の補語である DFA に変換するアルゴリズムを説明してください。補数は、A のアルファベットに関して取得する必要があります。構造が機能する理由についての非公式な議論が与えられます。正式な証明をする必要はありません。

どんな種類のガイダンスも大歓迎です...

4

1 に答える 1

0

受け入れ状態を非受け入れ状態に変換し、非受け入れ状態を受け入れ状態に変換することにより、FAをその補数に変換できます。簡単！

NFA状態をDFAに変換するには、任意のNFA状態が状態の累乗であると見なします。つまり、NFAの各状態について、アクティブまたは非アクティブのいずれかです。これらの各状態をDFAの状態にマップできるため、最終的には最大2つの|Q|になります。NFAを表すDFAの状態。

編集：このアルゴリズムとその証明は、それが有効な有限状態オートマトンである限り、実際にはAの詳細を必要としません。

于 2011-04-18T07:11:23.793 に答える