下推自動機的語言

Question

我想設計一個下推自動機的語言

L = { a^i b^j c^k | i = j or k <= j <= 2k} 

是如右圖所示，如下圖中由教師提出的解決方案。

但我這裏關心的是，它不處理字符串的形式，當|2c| > |b|。那就是在q8狀態下，如果所有的B都堆疊出來，但輸入C還沒有完成。這裏沒有捕捉到這種轉變。

我的關注是否正確？ 或建議的解決方案是一個正確的PDA。

Answer 1

記住j> = k，這意味着| b | > = | c |。

如果輸入中的所有「b」都被讀取，則B的堆棧數量大於（或等於）要在輸入中讀取的「c」的數量。

• 如果j = k，那麼它將使用從q8到q8的轉換，直到輸入完成。
• 如果j = 2k，它會讀取一個「c」（q8 - > q9）並從堆棧中取出兩個B（q9 - > q8），所以只有字符串| b | = 2 | c |可以接受。
• 如果j < 2k，它將使用q8-> q9和q9-> q8，直到堆棧的數量等於要在輸入中讀取的「c」的數量。然後它將使用q 8-> q8直到輸入完成。