1

I have following language over the alphabet {1,0} L = {w | every prefix of w has no more 1's than 0's}

How can I construct an NPDA M from G such that L(M) = L(G)? Or To do that conversion, can one recommend any webpage?

4

1 回答 1

0

一般来说,为语言构建 NPDA 的方法只是找到语法,因为 CFG 和 NPDA 之间的映射相当简单。

这种语言的 CFG(上下文无关语法)类似于

S -> S "0" S | "" | S "0" S "1" S | S "1" S "0" S

一旦你有了上下文无关的语法,构建它的 NPDA 应该相对简单;)

顺便说一句,您在上面的帖子中没有提到 G 是什么,所以我假设您想要解释如何为所描述的语言构建 NPDA。如果你的意思是别的,告诉我,我会更新我的解释。

于 2011-05-11T06:39:39.473 回答