確定性有限狀態自動機問題

Question

我已經這個DFA描述爲（Q，Q 1，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 （2，a）→2，（2，b）→4,
（3，a）→2，（3，c）→4,
（3，c）→4,
4，b） - > 4，（4，C） - > 4}

因此，我已繪製的轉換圖，以及看起來不錯，

然後我需要解決閹羊或不以下字符串是由這個可接受的DFA：

1. 爲aabbcc
2. ACACAC
3. cabbac
4. BABBAB

，並拿出以下

1. 正確
2. 不正確（無法從移動？ - > C）
3. 不正確（無法從C -a動？ ）
4. 不正確（無法從b移動 - > A）

我不知道這些是正確的100％，但認爲他們是在正確的軌道上。

然後，我需要描述這種接受的語言，在英語中，我不認爲這是一個問題，但我需要幫助的地方是使用數學符號描述這種語言。你能幫我理解這一點嗎？

非常感謝您的幫助

Answer 1

你對字符串可接受的答案是正確的，這可以很容易地通過嘗試跟着他們出圖中可以看出。
現在，關於語言：

在2次頂點我們可以與對應的下面的正則表達式的話完成：
b?a+ - 我們可以任選地獲得b我的移動至3-RD頂點，然後再通過a，或者我們可以立刻移動到第2個頂點a，並且在那裏我們可以根據需要添加儘可能多的a。

現在大約在4個頂點整理的話：

首先，我們如何才能達到頂點4？
1.我們可以通過一次移動c來首次到達頂點4，或者先移動到第3個頂點，然後通過c移動到第4個頂點。在此我們得到如下的字符串：b?c
2.我們可以用b?a+（如前面的例子中所述）到達頂點2，然後通過b。在此我們得到像b?a+b這樣的字符串。
總的來說，我們可以使用與b?(a+b|c)正則表達式匹配的任何字來到達第4個頂點。

現在，在頂點4加入b和c符號任意的數量，最終，我們得到這種情況的答案：
b?(a+b|c)(bc)*

最後，我們可能會導致整組詞的可接受這個DFA的話，如下正則表達式：

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