0

在构造确定性下推自动机时，每个状态都可以是最终状态吗？

我在构建一个接受以下语言的 DPDA 时遇到了麻烦：

L = { 0 n 1 m | n ≥ m }

我的方法是使初始状态成为最终状态，可以将 0 推入堆栈以获取输入 0，然后转换到另一个最终状态，该最终状态可以从堆栈中弹出 0 以获取输入 1。我相信这个解决方案是正确的，但是每个状态都是最终状态似乎不寻常，我想验证我的方法是否有效。

这是正确的方法吗？我可以将两种状态都作为最终状态吗？这是我的 DPDA 的确切转换函数 δ。

δ(q 0 , 0, Z 0 ) = { (q 0 , 0 Z 0 ) }

δ(q 0 , 0, 0) = { (q 0 , 0 0) }

δ(q 0 , 1, 0) = { (q 1 , ε) }

δ(q 1 , 1, 0) = { (q 1 , ε) }

4

1 回答 1

1

当然，在确定性下推自动机中，每个状态都可以是最终状态。你的方法对我来说似乎是正确的。根据您对确定性的定义，可能还需要添加一个转换来处理您在状态 q_1 中读取 0 的情况，以便获得一个完整的转换函数（但这取决于您的上下文中的确定性定义为.)

于 2014-09-12T12:24:42.853 回答