資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學解釋確定性有限自動機 (DFA) 中的連線過程
下面解釋確定性有限自動機 (DFA) 中的連線過程：
如果 L1 和 L2 是兩個正則語言，則它們的交集 L1 ∩ L2 也是正則的。
例如：
L1 = {an | n > 0} 和 L2 = {bn | n > 0}
L3 = L1 ∩ L2 = {an ∩ bn | n > 0} 也是正則的。
在這個屬性中，我們說兩個 DFA 的連線也是 DFA。
問題
設計一個在字母表 {a,b} 上的 DFA，其中字串以 'a' 開頭並以 'b' 結尾。
解決方案
對於給定的條件，會形成兩種不同型別的語言，如下所示：
- L1 = {a, aab, aabab, .......}
- L2 = {b, bbab, bbabab, .......}
在 L1 中，起始元素是 'a'，
在 L2 中，結束元素是 'b'。
語言 L1
它以 'a' 開頭
L1 = {a, aab, aabab, .......}
L1 的狀態轉換圖如下所示：
在上圖的狀態轉換圖中，q1 是初始狀態。
DFA 中的每個狀態都必須對兩種輸入產生轉換
所以：
q1 對 'a' 轉到 q3 並達到其最終狀態 {a}。
q1 對 'b' 轉到 q2 並達到死狀態。
q3 對 'a' 轉到 q3，達到最終狀態，生成從起始狀態生成的字串 {a,ab,aba,aab,abb,……} 滿足每個字串都以 'a' 開頭的條件。
q2 是死狀態。
語言 L2
它以 'b' 結尾
L2 = {b, bbab, bbabab, .......}
L2 的狀態轉換圖如下所示：
初始狀態 q1：q1 對 'a' 轉到 q1
q1 對 'b' 轉到 q2
一旦我們生成字串 {ab,abb,abab,……}，它就滿足語言中每個字串都以 'b' 結尾的條件。
連線 L1 和 L2
當我們將 L1 和 L2 連線起來時，我們得到以下結果：
L = L1 ∩ L2 = L1.L2 = {ab, aab, abb, aaab, ...}
L1 和 L2 連線後的狀態轉換圖如下所示：
3K+ 瀏覽量
