可计算性和复杂性/形式语言/乔姆斯基层次结构/示例 PDA 输入
这些示例用于与 上下文无关语言 底部提供的 perl PDA 模拟器一起使用。该页面还包含关于 PDA 的描述及其工作原理。
接受任何形式为 的字符串的机器的规范
:States: q1 q2 q3 q4 :Start State: q1 :Accept States: q4 :alphabet: a b :stack alphabet: $ a :rules: q1 e e q4 $ q1 e e q2 $ q2 b a q3 e q2 a e q2 a q3 b a q3 e q3 e $ q4 e
一些示例输入：这些接受
a a b b
(the empty string)
a a a a a b b b b b
这些拒绝
a a a b b b b b
a a a b b
接受任何包含至少一个 'a' 以及至少同样多 'b' 的字符串的机器
:States: q1 q2 q3 q4 :Start State: q1 :Accept States: q4 :alphabet: a b :stack alphabet: $ a :rules: q3 b e q3 e q3 b a q3 e q2 b a q3 e q2 a e q2 a q1 e e q2 $ q3 e $ q4 e
一些示例输入：这些接受
a b
a a a b b b b b b b
这些拒绝
(the empty string)
a a a b b