数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究构造一个下推自动机 (PDA)，它接受 (a,b)* 语言，但不包含子串 bbbb。
下推自动机 (PDA) 是包含子串 bbb 的 PDA 的补集。
步骤
创建一个 PDA 来接受包含子串 bbb 的字符串。
通过将非接受状态设为接受状态，反之亦然，来取其补集。
构造 PDA
您可以像下面所示那样为(a,b)* 语言构造 PDA
转换格式的性质是：输入、栈顶、PUSH/POP
示例
a , a , aa 表示当输入为 a 且栈顶为 a 时，压入 a
在 q0（初始状态），如果输入是 a 或 b，则状态转移到 q1。
直到 q1 我们得到一个 b 来构成子串 b_ _，现在如果在 q1 输入 a，则会破坏 bbb 的模式。所以像上面 PDA 中所示那样转移到 q0。
但是如果得到 b, b, bb，这意味着输入是 b 且栈顶是 b。压入 bb，现在模式是 bb_，并转移到状态 q2。
现在在 q2，我们得到 2 个 bb 来构成子串 bb_。现在，如果在 q2 输入 a，则会破坏 bbb 的模式。所以像上面 PDA 中所示那样转移到 q0。
但是如果得到 b, b, bb，这意味着输入是 b 且栈顶是 b。压入 bb，现在模式是 bbb，并转移到状态 q4。
在状态 q4，我们已经完成了子串 bbb。所以现在，接受 a 或 b 任何符号。
当整个字符串结束且状态为 q4 时，我们转移到状态 q5。
现在，如果我们想要接受包含 bbb 作为子串的字符串的语言，那么 q5 是最终状态。
- 但是我们的问题是我们不想要 bbb。所以所有其他状态都是最终状态，即 q0、q1、q2、q4 都是最终状态。
所以，PDA 构造完成。
更新于：2021年6月16日
516 次浏览
广告