设计一个下推自动机来计算字符数

发布于 2024-10-02 10:59:54 字数 472 浏览 4 评论 0原文

字母表：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             #

等等......

原文

The Alphabet: a, b, c
I'm trying to define a PDA which accepts

 a^n b^m c^p : n + p = 2k for some integer k, m = k, and n, m, p, k >= 0

I think some strings that would be accepted are: #abc#; #aabbcc#; #aaabbbccc#; #abbccc#; #aaabbc# etc
The number of a's, b's and c's are not necessarily equal.

Start the head of the push down automata on the black space that is right most.

Usually I write my PDAs in columns:

State:    Symbol Read:    Next State:    Head Instruction:    
s         #               r1             Left
r1        c               r2             #

and so on...

分享到QQ

分享到微博

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

发布评论

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

毁梦 2024-10-09 10:59:54

我认为你描述的语言不是上下文无关的，因此不能
用 PDA 识别。问题是你需要强制执行约束
(n+p = 2m) 跨越任意长的子串，但不允许“泵送”（当
尝试使用上下文无关语言的泵引理构建证明）。

回复收藏 0 原文

神仙妹妹 2024-10-09 10:59:54

M=(K, E, q0, F, delta, stack_alphabet)
K={q0,q1,q2}
E={a,b,c,z}
F={q2}
stack_alphabet={a,b,z}
delta=
{
 *pop*     *push*
(q0, e, e)(q1, z)
(q1, a, e)(q1, a)
(q1, b, a)(q1, e)
(q1, b, z)(q1, bz)
(q1, c, b)(q2, e)
(q2, c, b)(q2, e)
}

M=(K, E, q0, F, delta, stack_alphabet)
K={q0,q1,q2}
E={a,b,c,z}
F={q2}
stack_alphabet={a,b,z}
delta=
{
 *pop*     *push*
(q0, e, e)(q1, z)
(q1, a, e)(q1, a)
(q1, b, a)(q1, e)
(q1, b, z)(q1, bz)
(q1, c, b)(q2, e)
(q2, c, b)(q2, e)
}

回复收藏 0 原文

~没有更多了~