下推式自動機的平衡圓括號和括號的語言

Question

我需要找出一個下推自動機來構造平衡圓括號和括號的語言字符串，比如this（（（[（））]））（） []。對於一種括號來說，似乎很容易;你的堆棧包括（當你看到它們時你推動，然後你彈出一個）。但是，我很難弄清楚這兩種括號。有沒有人有什麼建議？謝謝。

Answer 1

您遇到了麻煩，因爲您描述的語言不是上下文無關的（嘗試編寫它的上下文無關語法，這是不可能的），因爲Pumping Lemma不支持它。

直觀上，PDA只能「記住」一個數字，而您的語言需要「記住」以前看到的(和[的數量。

---

您的語言的一個子集是CF，嵌套和平衡括號和括號的語言。

的CF語法（我用3而不是小量這裏）：

S -> B | P | 3

B -> [B] | [P] | 3

P -> (B) | (P) | 3

和相關的PDA：

當它看到[，推b

當它看到(，推p

當它看到)，如果p是在它彈出它的堆棧的頂部，否則拒絕該字

當它看到]，如果b是在堆棧頂部它彈出它，否則它拒絕單詞