資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究如何在理論計算機科學（TOC）中將有限自動機（FA）轉換為左線性文法？
如果一個文法的產生式右側最多隻有一個變數，則稱為線性文法。
以下是一個線性文法的示例：
S→aSb/ε
在這裡，如果你觀察，我們可以透過劃分……來寫相同的產生式。
S→Ab
A→aAb
A→ε
左線性文法
如果一個文法的產生式右側所有非終結符都位於最左側，則稱為左線性文法。
例如：
A→Sa/ε
轉換步驟
將有限自動機（FA）轉換為左線性文法的步驟如下：
步驟 1 - 取有限自動機的逆
步驟 2 - 寫出右線性文法
步驟 3 - 然後取右線性文法的逆
步驟 4 - 最後，你將得到左線性文法
考慮如下所示的有限自動機：
將最終狀態作為初始狀態，將初始狀態作為最終狀態，如下所示：
現在移除不可達狀態，如下所示：
移除不可達狀態後，狀態轉換圖不是確定性有限自動機（DFA），因為狀態 A 沒有輸出符號，而狀態 B 在符號“a”上有兩個輸出。
因此，結果圖看起來像非確定性有限自動機（NFA）。
首先，為最終狀態轉換圖生成右線性文法：
B→aA/aB/bB
A→ε
現在反轉右線性文法以生成左線性文法：
B → Ba/Bb/Aa
A→ε
更新於：2021年6月12日
4K+ 次瀏覽
廣告