math - 決定論的有限状態オートマトンの質問

Question

このDFAは（Q、q1、A、N、F）と記述されています。

Q = {1,2,3,4}、
q1 = 1、
A = {a、b、c}、
F = {2,4}、
N = {
（1、a）-> 2、（1、b ）-> 3、（1、c）-> 4、
（2、a）-> 2、（2、b）-> 4、
（3、a）-> 2、（3、c）-> 4
（4、b）-> 4、（4、c）-> 4}

だから私は遷移図を描きました、そしてそれはうまく見えます、

次に、次の文字列がこのDFAで受け入れられるかどうかを判断する必要があります。

1. aabbcc
2. acacac
3. キャバック
4. ババブ

そして、次のことを思い付く

1. 正しい
2. 不正解（a-> cから移動できませんか？）
3. 不正解（c -aから移動できませんか？）
4. 不正解（b-> aから移動できません）

それらが正しいかどうかは100％わかりませんが、正しい方向に進んでいると思います。

次に、これが受け入れる言語を英語で説明する必要があります。これは問題ではないと思いますが、助けが必要なのは、数学表記を使用してこの言語を説明することです。これを理解するのを手伝っていただけませんか。

あなたの助けをどうもありがとう

Answer 1

文字列の受容性についてのあなたの答えは正しいです、これは図でそれらを追跡しようとすることによって簡単に見ることができます。
さて、言語について：

2番目の頂点では、次の正規表現に対応する単語で終了
b?a+できます。-オプションbで、最初に3番目の頂点に移動してから通過するaか、または2番目の頂点aに一度に移動することができます。そこで、必要なだけasを追加できます。

次に、4番目の頂点で単語を終了します。

まず、どのようにして頂点4に到達できますか？
1.最初に頂点4に到達するには、頂点4cに一度に移動するか、最初に3番目の頂点に移動してbを取得し、次に4番目に移動しcます。これにより、2のような文字列が得られます。（前のケースで説明したように）でb?c
頂点2に到達してb?a+から、を渡すことができbます。これにより、のような文字列が得られますb?a+b。全体として、正規表現
に一致する任意の単語で4番目の頂点に到達できます。b?(a+b|c)

ここで、頂点4の最後に任意の数の記号bとc記号を追加すると、この場合の答えが得られます。
b?(a+b|c)(bc)*

最後に、このDFA単語で受け入れられる単語のセット全体を次の正規表現として作成できます。

b?( a+ | (a+b|c)(bc)*? )