finite-automata - このDFAのδ（A、01）を解く方法は？

Question

DFAを検討してください：

δ（A、01）は何に等しくなりますか？ オプション：

A) {D}    
B) {C,D}      
C) {B,C,D}       
D) {A,B,C,D}

正解はオプションB）ですが、方法がわかりません。誰かがそれを解決するための手順を説明してください。また、一般的に、DFAと移行のためにどのように解決するのですか？

ありがとう。

Answer 1

B) 選択肢が不正解！この遷移グラフの場合。

Transition Graph(TG) の記号εはNULL-move ( ε-move) を意味します。TG には 2 つの NULL 技があります。

One:       (A) --- `ε` ---->(B)  
Second:    (A) --- `ε` ---->(C) 

ε-moveシンボルを消費せずに状態を変更できることを意味します。A to B、またはからのダイアグラムでA to C。

δ(A,01) は何に等しいでしょうか?

A「入力が「」の場合、状態からのパスは何ですか」という質問01。（最終状態は1つしかないので理解しています）

012 つの方法のいずれかで処理できます。

• (A) -- ε --->(B) -- 0 --> (B) -- 1 --> (D)

• (A) -- ε --->(C) -- 0 --> (B) -- 1 --> (D)

01また、最終状態に到達したくない場合でも、 文字列を処理する方法は他にありません。

[ ANSWER ]
では、問題の印刷ミスがあります (またはどちらかがありました)。

遷移グラフから NULL 移動を削除する方法を学習できます。また、DFA の正規表現の書き方

TG から null-moves を削除すると、3 つの方法で受け入れることができます01。

NULL-MOVE のない等価遷移グラフ

Graph には 3 つの開始状態があることに注意してください。

3 つの方法:

{ABD}  
{CBD}  
{BBD}     

すべてのオプションstate-(B)が来なければなりません。

また、あなたの書いていることConsider the DFA :は間違っています。非決定的な動き δ(A,ε) があり、次の状態が B または C のいずれかであるため、TG は決定論的ではありません。