automata - NFA から DFA への変換

Question

変換の仕方が分からなくて困っています。

2 が 'a' の入力を取得した場合、空の文字列のために (1,4) または (1,2,4) になりますか?

ありがとう！

Answer 1

状態Q2が「a」の入力を取得した場合、次の状態は、、、0rのいずれかQ1になります。 Q2Q4

NFAで最終状態を取得しますQ4

同等のDFAは次のとおりです。

                 a-  
                 ||
                 ▼|
--►(Q0)---a---►((Q1))---b----►((Qf))  
                 ▲-----a--------| 

Q1とは最終Q2状態です。

そして、その正規表現は次のとおりです。 a (a + ba)* (b + ε )

εnullシンボル（イプシロン）はどこにありますか

Answer 2

空入力クロージャー セットを識別して、NFA を DFA に変換し始めます (ここから始めて、i は L クロージャーによって空入力クロージャーを示します)。
L(1)=(1,2) 空の入力で 1 から 2 にアクセスできます。
L(2)=(2) 2 からの空の入力エッジはありません。
L(3)=(3) 3 からの空の入力エッジはありません。
L(4)=(1,2,4) できる4 から 1 と 1 から 2 を参照してください。

2 が 'a' の入力を取得した場合、空の文字列のために (1,4) または (1,2,4) になりますか?

2 が 'a' の入力を取得すると、L(1)UL(4)=(1,2,4) になります。

NFA では開始ノードが 1 であるため、DFA では (1,2) である L(1) になります。

T((1,2),a)=L(1)UL(3)UL(4)=(1,2,3,4)  
T((1,2),b)=F  
T((1,2,3,4),a)=L(1)UL(3)UL(4)=(1,2,3,4)  
T((1,2,3,4),b)=L(4)=(1,2,4)  
T((1,2,4),a)=L(1)UL(3)UL(4)=(1,2,3,4)  
T((1,2,4),b)=F  

NFA では 4 が受け入れノードであるため、DFA では 4 を含むノードが受け入れノード (1,2,3,4) と (1,2,4) になります。