接受语言L={a^n ^m\ n<m}

Question

我知道如何为mn的逻辑。

在m

我能为m>n做什么..。

Answer 1

初始结构是一样的。但你有两个不同的州来读b的：

• State B1:我在弹b，但堆栈不是空的。

- If the top of the stack is an 'a' and you read a 'b': stay in that state
- If the stack is empty and you read a 'b':  go to state B2

• State B2:我在弹出b‘s，堆栈是空的。

- If the top of the stack is empty and you read a 'b', stay in that state
- Otherwise fail.

如果你在州立大学( state B2 )，你读过比a更多的b。

Answer 2

由给定语言生成的字符串如下所示：−

L={a，abb，aabbbb，aabbbb，….)

这里没有。A的值小于0。B‘s

每当“a”出现时，推“a”，当“b”出现时，每次从堆栈中弹出“a”。为了进一步输入'b‘就像那样离开。最后，在字符串的末尾，如果堆栈中什么都没有留下，那么我们可以声明在PDA中接受语言。

该问题的PDA如下所示：−转换函数，转换函数如下，−

步骤1: q0，a，Z) = (q0，aZ)

步骤2: q0( a，a) = (q0，aa)

步骤3: q0 (q1，a) =(q1，ε)

步骤4: q1，b，a) = (q1，ε)

步骤5: q1，b，Z) = (qf，Z)

解释步骤1−考虑输入字符串："abb“，它满足给定条件。

步骤2−扫描字符串从左到右。

输入'a‘和堆栈字母表Z的步骤3−，然后将'a’推到堆栈中。

步骤4输入'b‘和堆栈字母表'a’的−，然后

从堆栈中弹出一个'a‘：(b，a/ε)，状态将是ε。

任何no的步骤5−。输入'b‘和堆栈Z和状态q1的顶部，然后移动到最终状态qf。

步骤6−我们到达字符串的末尾，输入ε和堆栈字母表Z

进入最终状态(Qf)：(ε，Z/Z)