字母表:a、b、c 我正在尝试定义一个接受的 PDA
a^n b^m c^p : n + p = 2k for some integer k, m = k, and n, m, p, k >= 0
我认为一些可以接受的字符串是:#abc#; #aabbcc#； #aaabbbccc#； #abbccc#； #aaabbc#等 a、b、c 的数量不一定相等。
从最右边的黑色空间开始下推自动机的头部。
通常我将我的 PDA 写在列中:
State: Symbol Read: Next State: Head Instruction:
s # r1 Left
r1 c r2 #
等等...
最佳答案
我认为你描述的语言不是上下文无关的，因此不能 用 PDA 识别。问题是你需要强制执行约束 (n+p = 2m) 跨越任意长的子串，但不允许“泵送”(当 尝试使用上下文无关语言的泵引理构建证明。
关于context-free-grammar - 设计一个下推自动机来计算字符数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4173653/