解釋 PDA 的平衡括號

下推自動機 (PDA) 是有限自動機 (FA)，但能夠將符號推入/彈出棧。

如果有輸入的啟動狀態到接受狀態的合法路徑，則 PDA 接受字串。否則，字串將被拒絕。

PDA 可以用 7 元組表示

(Q, ∑, ℾ, q₀, ha, ∆,δ)

其中

PDA 是 Q ☓ (ℾ ∪ {∆})* 的有限子集。

括號平衡，如果

• 在讀取字串時，左括號數量 >= 右括號數量
• 字串讀完後，左括號數量 = 右括號數量

示例

• (())() − 平衡
• ((()() − 不平衡
• )()(() − 不平衡

上下文無關文法 (CFG) 如下所示 −

S -> (S) | SS | ε

平衡括號的 PDA

每個 ( 被推入，每個 ) 導致 ( 被彈出。如下所示

Bhanu Priya

更新於：2021 年 6 月 16 日

5K+ 瀏覽

開啟你的 職業生涯

完成課程獲得認證

開始學習