資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學構造一個接受L = {anb(2n) | n>=1} ∪ {anbn | n>=1} 的下推自動機 (PDA)
下推自動機 (PDA) 可以形式化地描述為七元組
(Q, Σ,S, δ,q0,I,F)
其中：
- Q 是有限數量的狀態
- Σ 是輸入字母表
- S 是棧符號
- Δ 是轉移函式: QX(Σ∪{e})XSXQ
- q0 是初始狀態 (q0屬於Q)
- I 是初始棧頂符號
- F 是一組接受狀態
問題
構造 PDA 用於 L = {anb(2n) | n>=1} ∪ {anbn | n>=1}
解答
設
L = {anb(2n) | n>=1}
{anbn | n>=1}
構造 PDA 用於 L= L1 U L2
因此，由給定語言 L1 生成的字串如下：
L1={abb,aabbbb,aaabbbbbb,….} 和
L2= {ab,aabb,aaabbb,….}
L= L1 U L2 = { abb,aabbbb,aaabbbbbb,….} U {ab,aabb,aaabbb,….}
對於語言 L1
在該語言中，a 後面跟著兩倍數量的 b。
每當出現 ‘a’ 時，在棧中壓入兩個 ‘a’；如果再次出現 ‘a’，則重複此操作。
當出現 ‘b’ 時，每次從棧中彈出 一個 ‘a’。注意 b 出現在 ‘a’ 之後。
最終，如果字串結束時棧為空，則可以宣告 PDA 接受該語言。
對於語言 L2
對於語言 L2，我們必須計算相等數量的 a 和 b。
這可以透過在棧中壓入 a，然後在出現 "b" 時彈出 a 來實現。
最終，如果字串結束時棧為空，則可以宣告 PDA 接受該語言。
該問題的 PDA 如下：
轉移函式
轉移函式如下：
步驟 1: δ(q0, a, Z) = (q1, aZ)
步驟 2: δ(q0, a, a) = (q3, aaz)
步驟 3: δ(q1, a, a) = (q1, aa)
步驟 4: δ(q1, b, a) = (q2, ε)
步驟 5: δ(q2, b, a) = (q2, ε)
步驟 6: δ(q2, ε, Z) = (qf1, Z)
步驟 7: δ(q3, a, a) = (q3, aaa)
步驟 8: δ(q3, b, a) = (q4, ε)
步驟 9: δ(q4, b, a) = (q4, ε)
步驟 10: δ(q4, ε, Z) = (qf2, Z)
2K+ 瀏覽量
