如何找出以下NPDA接受的语言

Question

我想了解如何找到以下 NPDA 将接受的语言。

M = {Q, Σ, Τ, δ, q0, z, F}
Q is a set of state: {q0, q1, q2}
Σ is alphabet: {a, b}
Τ is stack alphabet: {0, 1, z}
δ is transition function
z is stack start symbol
F is set of final state.

而且，它的转换函数如下。

δ(q0, a, z) = {(q1 , 0), (q2 , λ)}
δ(q1, b, 0) = {(q1, 1)}
δ(q1, b, 1) = {(q1, 1)}
δ(q1, a, 1) = {(q2, λ)}

Answer 1

基于这些转换，我假设最终状态是 q2 并且接受空栈（看起来它甚至去掉了栈底符号 z，这对我来说有点不寻常，但我想这很好）。

过渡是这些：

δ(q0, a, z) = {(q1 , 0), (q2 , λ)}
δ(q1, b, 0) = {(q1, 1)}
δ(q1, b, 1) = {(q1, 1)}
δ(q1, a, 1) = {(q2, λ)}

让我们一个接一个。

δ(q0, a, z) = {(q1 , 0), (q2 , λ)} 意味着如果我们处于初始状态并且我们看到 a，我们可以转到状态 q1 并替换 z 和 0，或者我们可以去掉 z 并进入状态 q2。这实际上是 NPDA 的接受配置；这意味着 NPDA 接受空字符串，并且我们确定的任何语言也必须包含该字符串。因为离开初始状态 q0 的唯一其他方法是看到 a，我们还知道我们语言中的任何非空字符串都必须以 a.[=49= 开头]
δ(q1, b, 0) = {(q1, 1)} 意味着如果我们现在处于状态 q1，请在输入中看到一个 b 并且在 0堆栈，我们可以将堆栈符号更改为1。一旦我们从 q0 进入状态 q1，我们将处于此配置中。请注意，由于没有其他转换将 0 放在堆栈顶部，因此这是唯一一次可以使用此转换；事实上，它必须被使用，因为 q1 不接受，我们必须通过这个转换来清除堆栈顶部的 0。因此，该语言中的所有非空字符串都必须以 ab.
δ(q1, b, 1) = {(q1, 1)} 意味着如果我们处于状态 q1，在输入中看到一个 b 并且在其顶部有一个 1堆栈，我们可以永远消耗更多 bs。只要我们在输入中有更多 b，我们就会保持这种配置。然而，我们不一定需要经历这个状态：还有其他转换将 1 放在堆栈顶部，而通往接受状态的路径可能根本不涉及此转换。此转换让我们可以在上次转换中看到的所需 b 之后放置任意数量的 b。
δ(q1, a, 1) = {(q2, λ)} means that if we're in stateq1, see anain the input and have a1on top of the stack, we can erase the stack and go to the accepting state. This means that any non-empty string in the language ends with a singlea`.

回顾一下：

空字符串是语言
该语言中的任何非空字符串都以 ab
该语言中的任何非空字符串中间都可以有任意数量的 b
该语言中的任何非空字符串都以 a 结尾。

将所有这些放在一起，我们发现一个正则表达式描述了该语言：e + abb*a。我们不应该对此感到惊讶，因为这个 NPDA 的堆栈中只包含零到两个元素；因为使用的堆栈数量是恒定的，NPDA 相当于一些 DFA，因此它的语言必须是正则的。

如何找出以下NPDA接受的语言

How to find out the language that accepted by below NPDA

computer-science

automata

automata-theory