下推一种语言的自动机
Push down automata for a language
我想为该语言设计一个下推自动机
L = { a^i b^j c^k | i = j or k <= j <= 2k}
老师提出的解决方案如下图所示。
但我担心的是，它不处理 |2c| > |b| 形式的字符串。也就是在q8状态下，如果所有的B都出栈了，但是C还没有输入完呢。此处未捕获该转换。
我的担心对吗？
或者建议的解决方案是正确的 PDA。
记住 j >= k，所以这意味着 |b| >= |c|.
如果input中所有的"b"都被读取，那么B的堆叠个数大于（或等于）input中要读取的"c"个数。
- 如果 j = k，那么它将使用从 q8 到 q8 的转换，直到输入完成。
- 如果 j = 2k，它将读取一个 "c" (q8 -> q9) 并从堆栈中取出两个 B (q9 -> q8)，因此只有带有 |b| 的字符串= 2|c|可以接受。
- 如果 j < 2k，它将使用 q8 -> q9 和 q9-> q8，直到堆叠的 B 的数量等于输入中要读取的 "c" 的数量。然后它将使用 q 8-> q8 直到输入完成。
我想为该语言设计一个下推自动机
L = { a^i b^j c^k | i = j or k <= j <= 2k}
老师提出的解决方案如下图所示。
但我担心的是，它不处理 |2c| > |b| 形式的字符串。也就是在q8状态下，如果所有的B都出栈了，但是C还没有输入完呢。此处未捕获该转换。
我的担心对吗？ 或者建议的解决方案是正确的 PDA。
记住 j >= k，所以这意味着 |b| >= |c|.
如果input中所有的"b"都被读取，那么B的堆叠个数大于（或等于）input中要读取的"c"个数。
- 如果 j = k，那么它将使用从 q8 到 q8 的转换，直到输入完成。
- 如果 j = 2k，它将读取一个 "c" (q8 -> q9) 并从堆栈中取出两个 B (q9 -> q8)，因此只有带有 |b| 的字符串= 2|c|可以接受。
- 如果 j < 2k，它将使用 q8 -> q9 和 q9-> q8，直到堆叠的 B 的数量等于输入中要读取的 "c" 的数量。然后它将使用 q 8-> q8 直到输入完成。