下面显示的 PDA 接受的语言是什么
What is the language accepted by the PDA shown below
我不确定我对这个问题的回答。
当我跟进问题时,我的答案是
{a^nb^ma^n | m,n∈ N,m,n>=0}
这样对吗?有人可以检查我的答案吗?
假设这个PDA只接受状态接受,栈内容无关紧要
然后它接受以下所有内容:
- bb*,从状态 0
立即看到 b
- (aa)*,通过在状态 0 和 2 之间循环
- (a^n)b*(a^n) for n > 0 通过读取状态 0 和 2 中的 n a,然后读取状态 3 中的任意数量的 b,然后读取状态 4 中的 n a .
第 3 项是您所识别的,只是它不包含空字符串。但是,我们的第 2 项包含空字符串,因此在这一点上您没问题。因此,您的语言不包含任何不属于该语言的内容;你的语言是我的一个子集。
但我的语言也是您的子集,因为第 1 项仅对应于您语言中 n = 0 的所有非空字符串,而我的项目 2 对应于您语言中 m = 0 的所有字符串.
因为你和我的语言互为子集,它们是相同的,而且你的渲染比我的更紧凑和优雅。所以,我们同意您的答案是正确的。
我不确定我对这个问题的回答。 当我跟进问题时,我的答案是
{a^nb^ma^n | m,n∈ N,m,n>=0}
这样对吗?有人可以检查我的答案吗?
假设这个PDA只接受状态接受,栈内容无关紧要
然后它接受以下所有内容:
- bb*,从状态 0 立即看到 b
- (aa)*,通过在状态 0 和 2 之间循环
- (a^n)b*(a^n) for n > 0 通过读取状态 0 和 2 中的 n a,然后读取状态 3 中的任意数量的 b,然后读取状态 4 中的 n a .
第 3 项是您所识别的,只是它不包含空字符串。但是,我们的第 2 项包含空字符串,因此在这一点上您没问题。因此,您的语言不包含任何不属于该语言的内容;你的语言是我的一个子集。
但我的语言也是您的子集,因为第 1 项仅对应于您语言中 n = 0 的所有非空字符串,而我的项目 2 对应于您语言中 m = 0 的所有字符串.
因为你和我的语言互为子集,它们是相同的,而且你的渲染比我的更紧凑和优雅。所以,我们同意您的答案是正确的。