解释 PDA 的平衡括号

下推自动机 (PDA) 是有限自动机 (FA)，但能够将符号推入/弹出栈。

如果有输入的启动状态到接受状态的合法路径，则 PDA 接受字符串。否则，字符串将被拒绝。

PDA 可以用 7 元组表示

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

其中

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

括号平衡，如果

• 在读取字符串时，左括号数量 >= 右括号数量
• 字符串读完后，左括号数量 = 右括号数量

示例

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

上下文无关文法 (CFG) 如下所示 −

S -> (S) | SS | ε

平衡括号的 PDA

每个 ( 被推入，每个 ) 导致 ( 被弹出。如下所示

Bhanu Priya

更新于：2021 年 6 月 16 日

5K+ 浏览

开启你的 职业生涯

完成课程获得认证

开始学习