构造一个用于语言 L = {0ⁿ1^m2^m3ⁿ | n≥1, m≥1} 的下推自动机 (PDA)。

下推自动机 (PDA) 可以形式化地描述为七元组

(Q, Σ, S, δ, q₀, I, F)

其中，

• Q 是有限数量的状态
• Σ 是输入字母表
• S 是栈符号
• Δ 是转移函数：Q × (Σ ∪ {e}) × S → Q × S*
• q₀ 是初始状态 (q₀ ∈ Q)
• I 是初始栈顶符号
• F 是接受状态集 (F ⊆ Q)

问题

构造一个用于语言 0ⁿ1^m2^m3ⁿ (其中 n, m ≥ 1) 的 PDA。

解答

因此，由给定语言生成的字符串为：

L = {0123, 011223, 001233…}

1 的数量和 3 的数量相同，2 的数量和 1 的数量相同。

给定问题的 PDA 构造

PDA 如下：

解释

**步骤 1** - 首先将 0 入栈。

**步骤 2** - 接下来将 1 入栈。

**步骤 3** - 对于每个输入的 2，弹出栈顶的一个 1。

**步骤 4** - 如果仍然有剩余的 2，并且栈顶是 0，则该字符串不被 PDA 接受。

**步骤 5** - 如果 2 已处理完毕，并且栈顶是 0，则对于每个输入的 3，弹出相同数量的 0。

**步骤 6** - 如果字符串处理完毕并且栈为空，则该字符串被 PDA 接受。否则，该字符串不被接受。

Bhanu Priya

更新于：2021年6月15日

6K+ 次浏览

开启你的职业生涯

完成课程获得认证

开始学习