grammar - この決定性有限オートマトンの言語は何ですか？

Question

与えられた：

受け入れられている言語が何であるかわかりません。

それを見ると、いくつかの最終結果を得ることができます。

1.) bb
2.) ab(a,b)
3.) bbab(a, b)
4.) bbaaa

Answer 1

How to write regular expression for a DFA

In any automata, the purpose of state is like memory element. A state stores some information in automate like ON-OFF fan switch.
A Deterministic-Finite-Automata(DFA) called finite automata because finite amount of memory present in the form of states. For any Regular Language(RL) a DFA is always possible.

Let's see what information stored in the DFA (refer my colorful figure).
(note: In my explanation any number means zero or more times and Λ is null symbol)

---

State-1: is START state and information stored in it is even number of a has been come. And ZERO b.
Regular Expression(RE) for this state is = (aa)*.

状態-4:奇数aが来ました。そしてゼロb。
この状態の正規表現は= (aa)*aです。

Figure: a BLUE states = EVEN number of a, RED states = ODD number ofa来た。

注意:最初のbが来ると、状態 1 と状態 4 に戻ることはできません。

状態-5: の後に続きYellow bます。Yellow b を意味し b after odd numbers of aます。(状態 5 で)奇数
を取得すると、状態 5 で (b,a) の自己ループがあるため、すべてが受け入れられます。 ba

state-5 の場合は次のように書くことができます: Yellow-b に続く a, b の任意の文字列= Yellow-b (a + b)*

State-6:奇数か偶数かを区別するためだけにa。

状態 2: の後にa続きbますb。= (aa)* bb*

状態 3:状態 2 の後に続き、最初aに状態 6 を経由するループがあります。状態 3 について書くことができます= state-2 a (aa)* = (aa)*bb* a (aa)*

私たちの DFA には 3 つの最終状態があるため、DFA で受け入れられる言語は 3 つの RL (または 3 つの RE) の和集合 (RE の +) です。
したがって、DFA によって受け入れられる言語は、3 つの受け入れ状態 (2、3、5 ) に対応します。次のように記述できます。

 State-2 +  state-3           + state-5    

(aa)*bb* + (aa)*bb* a (aa)*+Yellow-b (a + b)*

説明するのを忘れていましたhow Yellow-b comes?
ANSWER:状態 4 または状態 3Yellow-bの後です。bそして、次のように書くことができます:

Yellow-b = ( state-4 + state-3 ) b = ( (aa)*a+ (aa)*bb* a (aa)*)b

【回答】
(aa)*bb* + (aa)*bb* a (aa)*+ ( (aa)*a+ (aa)*bb* a (aa)*)b (a + b)*

---

言語の英語記述: DFA は 3 つの言語の和集合を受け入れます

• 偶数aの の後に 1 つ以上の が続きますb。
• 偶数aの の後に 1 つ以上の が続きb、その後に奇数の が続きますa。
• aANDの接頭辞文字列で、b奇数a個の が続き、その後にAND ANDのb任意の文字列が続きます。 abΛ

英語の説明は複雑ですが、これが言語を説明する唯一の方法です。最初に特定の DFA を最小化された DFA に変換してから、RE と説明を記述することで改善できます。

---

また、 Arden の定理を使用して、特定の遷移グラフから RE を見つける微分法もあります。Arden の定理を使用して DFA の正規表現を記述する方法をここで説明しました。遷移グラフは、最初に null-move と single start 状態のない標準形式に変換する必要があります。しかし、私は数学的導出アプローチを使用する代わりに、分析によって計算の理論を学ぶことを好みます.

Answer 2

この質問はもう関係ないと思います:)そして、答えを述べるだけでそれを案内する方がおそらく良いでしょうが、それをカバーする基本的な式を取得したと思います（おそらく最小化可能です）ので、それを書きます将来の検索者のために

(aa)*b(b)* // for stoping at 2
U
(aa)*b(b)*a(aa)* // for stoping at 3
U
(aa)*b(b)*a(aa)*b((a)*(b)*)* // for stoping at 5 via 3
U
a(aa)*b((a)*(b)*)* // for stoping at 5 via 4

Answer 3

そこに記載されている例 (1 ～ 4) は、DFA で受け入れられている言語ではありません。これらは、DFA が受け入れる言語に属する単なる文字列です。したがって、それらはすべて同じ言語に分類されます。

その DFA を定義する正規表現を理解したい場合は、 k-path 誘導と呼ばれるものを実行する必要があります。これについては、こちら を参照してください。