当前位置：文江博客话题详情

PDA问题>需要帮助

发布于 2024-10-26 05:30:19 字数 103 浏览 3 评论 0原文

我的任务是构造一个能识别语言 A= {a^mb^n | m＞ n} 与 Σ = {a, b}.. 我有点困惑如何做到这一点.. 你们能帮我解决这个问题吗？谢谢

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

月隐月明月朦胧 2024-11-02 05:30:19

查看 Wikipedia 页面上下推自动机的示例：它适用于语言 { 0ⁿ1ⁿ | n ≥ 0}，即一定数量的零后跟相同数量的一。这与您的任务不完全相同，但相似。您能根据您的课程材料理解描述吗？您将如何修改它以识别您需要的语言？

回复收藏 0 原文

梦幻之岛 2024-11-02 05:30:19

我们先不要直接跳到为该问题设计 PDA，而是先尝试理解该问题。

给定语言可以生成哪些可能的字符串。
那么可以有无限个这样的字符串，例如 -

aab
aaab
aaa...b
aaaa..bb

这个想法是确保 a 的数量始终大于 b 的数量，或者我们可以说 a 中 b 的数量字符串不应超过 PDA 接受的字符串中 a 的数量。

现在我们有一个问题。

如何确保 a 的数量大于 b 的数量

对于一个字符串，如果我们开始取消字符串中每个 'b' 的 a
我们将得到以下结论

a 的数量等于 b 的数量 - 取消后什么都没有留下
b 的数量大于 a 的数量 - 我们是取消后只剩下几个 b
a 的数量大于 b 的数量 - 取消后我们留下了几个 a

如果我们尝试在“问题”和上面的那些点之间建立关系，我们会观察到该字符串属于上述第3点的字符串是PDA可接受的字符串。

现在让我们将 PDA 定义如下

P = ({q0,q1,qf}, {a,b}, δ, {a,b,Z0}, q0, Z0, {qf})

函数 (δ):

δ(q0, a, Z0) = (q0,aZ0)  
δ(q0, a, a) = (q0, aa)  
δ(q0, b, a) = (q1, Λ)  
δ(q1, b, a) = (q1, Λ) 
δ(q1, Λ, a) = (qf, Z0) 
δ(q1, b, Z0) = (q2, Z0)  
δ(q1, Λ, Z0) = (q2, Z0)

解释：

我们最初将 a 存储在堆栈中（q0 状态）
当遇到第一个 b 时，我们从堆栈中弹出 a 并将状态更改为 q1
我们继续从堆栈中弹出 a
如果没有剩余的 b 可以从中弹出 a stack 我们将状态更改为 qf 以指示字符串接受。 （第 3 点）
如果 b 所剩无几，但没有 a 从堆栈中弹出，我们将状态从 q1 更改为 q2（陷阱）。 （第 2 点）
如果堆栈中既没有留下要弹出的 a，也没有在输入字符串中留下 b，我们再次将状态从 q1 更改为 q2（陷阱）。 （第一点）

Let's not jump directly on to designing a PDA for the problem, and try to understand the question first.

What are few possible string that can be generated from the given language.
Well there can be infinite such string, for instance -

aab
aaab
aaa...b
aaaa..bb

The idea is to make sure that number of a's is always greater than number of b's, or we can say that number of b's in a string should never exceed number of a's in the string to be accepted by the PDA.

So now we have a question.

How to make sure that number of a's greater than number of b's

For a string if we start to cancel a's for every 'b' in the string
We will be left with the following conclusion

Number of a's was equal to number of b's - There was nothing left after cancellation
Number of b's was greater than number of a's - We were left with few b's after cancellation
Number of a's was greater than number of b's - We were left with few a's after cancellation

If we try to establish a relationship between 'Question' and those points above we observe that string which belong to Point No. 3 above are the strings acceptable by the PDA.

Now lets define our PDA as follows

P = ({q0,q1,qf}, {a,b}, δ, {a,b,Z0}, q0, Z0, {qf})

Transition function (δ):

δ(q0, a, Z0) = (q0,aZ0)  
δ(q0, a, a) = (q0, aa)  
δ(q0, b, a) = (q1, Λ)  
δ(q1, b, a) = (q1, Λ) 
δ(q1, Λ, a) = (qf, Z0) 
δ(q1, b, Z0) = (q2, Z0)  
δ(q1, Λ, Z0) = (q2, Z0)

Explanation:

We initially store a's in the stack (q0 state)
When first b is encountered, we pop a from stack and change state to q1
We continue popping a's from stack
If there is no b's left to pop a from stack we change the state to qf to indicate the string acceptace. (POINT No. 3)
If there are few b's left but there is no a to pop out from stack, we change state from q1 to q2(Trap). (POINT No. 2)
If neither a's is left in stack to be popped out nor b's are left in input string, we again change the state from q1 to q2(Trap). (POINT No. 1)

回复收藏 0 原文

~没有更多了~