math - constructing npda from given language| how

Question

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?

Answer 1

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

这种语言的 CFG（上下文无关语法）类似于

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

一旦你有了上下文无关的语法，构建它的 NPDA 应该相对简单；）

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