「語言的DFA」的定義

Question

我剛剛開始學習本學期的計算理論，並被「DFA for a language」一詞所困惑。如果要求爲某些二進制字符串L的集合構造一個DFA，是否意味着要找到L（M）= L或者僅僅是$ L（M）\ supset L $的DFA M？

Answer 1

大多數編譯器/理論課程傾向於圍繞確定性有限自動機和形式化語言的教學定義而存在不同的風格，但我會嘗試儘可能使這種描述不可知。

短語「語言的DFA」鬆散地表示：DFA接受語言中的每個word，並拒絕不在語言中的每個word。 我被教給的DFA的方式是讓最終/接受狀態和常規狀態消除隱含錯誤狀態的必要性。 這意味着，如果DFA在輸入末尾處的狀態爲accepting，則DFA接受該單詞，如果該狀態不是accepting，則該單詞拒絕該單詞。

例：

讓我們定義L，以含有偶數個1的語言。這些將是二進制字符串，因此這些符號僅爲0和1. 00，110， 111 ，1111等等是這種語言中單詞的示例。請注意，空字符串是用這種語言編寫的。

我們可以在我們的DFA中擁有兩種狀態。起始狀態，我們稱之爲even 1s，也是一個接受狀態，因爲0個狀態是偶數。另一種狀態是odd 1s，這是不能接受的。

至於轉換，當even 1s收到1時，它轉換爲odd 1s。當odd 1s收到1時，它轉換爲even 1s。 現在，0的數量並不重要，所以在任何一種狀態下，它都會轉變爲自身。

道歉的雙箭頭，這website是偉大的，但我無法弄清楚如何過渡even 1s和odd 1s

之間分開

Answer 2

用精確的方式寫下你的問題。這裏的語言DFA意味着您需要爲特定語言構建機器，而不是它的子集或超集。構造L（M）= L的DFA矩陣。