資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學如何將有限自動機 (FA) 轉換為右線性正則文法？
最多隻有一個變量出現在產生式右邊的文法稱為線性文法。
示例 1
S→aSb/ε
示例 2
S→Ab
A→aAb
A→ε
右線性文法
右線性文法是指所有非終結符都在右端出現的文法。
例如：
S->aS/ε
轉換演算法
將有限自動機 (FA) 轉換為右線性文法的演算法如下：
步驟 1 - 從起始狀態開始。
步驟 2 - 對每個狀態重複此過程。
步驟 3 - 將產生式作為輸出，後跟轉換所到達的狀態。
步驟 4 - 最後，新增 € (epsilon) 來結束推導。
示例 1
讓我們考慮如下所示的有限自動機 (FA)：
選擇起始狀態 A，在符號 'a' 上的輸出到達狀態 B
A→aB
現在我們將選擇狀態 B，然後我們將繼續每個輸出
即 B→aB
B→bB
B→ε
因此，
最終的右線性文法如下：
A→aB
B→aB/bB/ε
示例 2
從狀態 A 開始，它是初始狀態，在符號 'a' 上的輸出到達 A 和 B，在符號 'b' 上的輸出到達 A。現在右線性文法的產生式規則是：
A→aA/bA/aB
現在選擇狀態 B，然後繼續每個輸出，右線性文法是：
B→aB/bB/ε
給定有限自動機的最終右線性文法是：
A→aA/bA/aB
B→aB/bB/ε
更新於：2021年6月12日
6K+ 次瀏覽
廣告