regex - DFA への正規表現

Question

添付の DFA が正しいかどうか教えてもらえますか?

アルファベット Σ ={a, b} を持つ言語に DFA を与えるとします。

これにはDFAが必要です ----> A={ε, b, ab}

Answer 1

いいえ、複数の理由から:

1. あなたのオートマトンbab
2. あなたのオートマトンは受け入れませんab
3. 少なくともいくつかの厳密な定義によると、オートマトンはDFAではありません

最初のポイントについて: から始めてq1、 を見てb、 に行き、 をq2見て、 にa行き、 をq3見て、bに行きq4ます。私たちはそれを見babて受け入れました。

2 番目の点について: から開始するとq1、a遷移が定義されていません。オートマトンは「クラッシュ」し、受け入れられません。そのため、 を含め、 で始まる文字列aは受け入れられませんab。

3 番目の点について: 多くの場合、DFA はすべての状態と遷移を表示する必要があります。これには、受理状態に戻ることのないデッド状態と遷移が含まれます。オートマトンのすべての遷移とすべての状態を表示するわけではありません。

Myhill-Nerode の定理を使用して、言語の最小 DFA に含まれる状態の数を決定できます。空の状態には、空の文字列を追加するか、b言語abで文字列を取得することができます。追加aできます。空の文字列を追加できますb。、、または言語で文字列を取得するためbに何も追加することはできません(したがって、これらは区別できません)。ただし、空の文字列を追加できます (したがって、 と区別できません)。aabbbaabb

そのように決定された等価クラスは、最小 DFA の状態に対応します。等価クラスは次のとおりです。

1. 空の文字列のような文字列
2. のような文字列b
3. のような文字列a
4. のような文字列aa

は言語にあることに注意してくださいb。したがって、2 番目のクラスは受け入れ状態に対応します。言語で文字列を取得するために何も追加できないことがわかりaaます。そのため、このクラスは DFA のデッド状態に対応します。これらの状態間の遷移は、新しいシンボルの追加によってどの新しい等価クラスに置かれるかを確認することで記述します。

1. 空の文字列にa追加すると (3) にあるものが得られるため、追加すると (3) になります。空の文字列に追加すると (2) にあるものが得られるため、追加すると (2)になります。aabbb

2. aに追加aすると(4) になりbます。これは、言語の文字列のプレフィックスではないという点でba似ています。aaを追加bすると、同様の議論によって (4) に到達します。

3. 追加aするaaと、(4) になります。これを追加bすると、(2) になります。abb

4. デッド ステートからのすべての遷移は、デッド ステートに戻ります。両方ともa( b4) に戻ります。

あなたは次のようなものになります：

q1 --a--> q3
 |        /|
 b  --b--< a
 | /       |
 vv        v
q2 -a,b-> q4 \
           ^ a,b
           \_/

または表形式で：

q    s    q'
==   =    ==
q1   a    q3
q1   b    q2
q2   a    q4
q2   b    q4
q3   a    q4
q3   b    q2
q4   a    q4
q4   b    q4

Answer 2

この DFA はその言語に適していると思います。