使用C++构建用于语言L = {0(n+m)1m2n | m, n = 0}的下推自动机。

给定一种语言“L”，任务是为该语言构建一个下推自动机。该语言说明0的出现次数将等于1和2的出现次数之和，并且1和2的出现次数至少为1（也可以使字符串为空），并且该自动机应该接受该字符串。

什么是下推自动机？

下推自动机或PDA是一种实现上下文无关文法的方法，类似于我们为正则文法设计确定性有限自动机或DFA的方式。DFA可以处理有限数据，但PDA可以处理无限数据。我们可以将下推自动机理解为“有限状态机”和“栈”的组合。

下推自动机有三个组成部分：

  • 输入带，

  • 控制单元，以及

  • 一个无限大小的栈。

PDA可以形式化地描述为一个7元组 (Q, Ʃ, S, δ, q0, I, F) ：

  • Q 是有限数量的状态

  • Ʃ 是输入字母表

  • S 是栈符号

  • δ 是转移函数：Q × (Ʃ υ {ε}) × S × Q × S*

  • q0 是初始状态 (q0 ε Q)

  • I 是初始栈顶符号 (I ε S)

  • F 是一个接受状态集 (F ε Q)

**让我们为给定的语言构建一个下推自动机**：

该PDA可以接受的字符串形式为：

  • 1. 0n2n：02、0022、000222等。0的个数等于2的个数。当m为0时，没有1。不断压入0，一旦遇到第一个2，则弹出0。如果到达字符串末尾并且没有剩余0，则接受该字符串。

  • 0m1m：01、0011、000111等。0的个数等于1的个数。当n为0时，没有2。不断压入0，一旦遇到第一个1，则弹出0。如果到达字符串末尾并且没有剩余0，则接受该字符串。

  • 0n+m1m2n：0012、000112、000122等。0的个数等于1和2的个数之和。不断压入0，一旦遇到第一个1，则弹出0直到没有1。然后再次压入0，一旦遇到第一个2，则弹出0直到没有2。该字符串将被接受。

  • 空字符串也被接受。001020

让我们了解一下这个机器

  • 状态q0的转移

    • (0, I/0I) - 如果栈顶为I且当前输入符号为0，则将0压入栈顶并保持在q0。栈变为0I…

    • (0, 0/00) - 如果栈顶为0且当前输入符号也为0，则将0压入栈顶并保持在q0。栈变为00… 不断压入0直到下一个1或2。

    • (1, 0/$) - 如果栈顶为0且当前输入符号为1，则弹出0并移动到q1。

    • (2, 0/$) - 如果栈顶为0且当前输入符号为2，则弹出0并移动到q2。

    • ($, I/I) - 如果栈顶为I且没有输入，则不做任何操作并移动到qf。对于空字符串。

  • 状态q1的转移：

    • (1, 0/$) - 如果栈顶为0且当前输入符号为1，则弹出0并保持在q1。

    • ($, I/I) - 如果栈顶为I且没有输入，则不做任何操作并移动到qf。

    • (2, 0/$) - 如果栈顶为0且当前输入符号为2，则弹出0并移动到q2。

  • 状态q2的转移：

    • (2, 0/$) - 如果栈顶为0且当前输入符号为2，则弹出0并保持在q2。

    • ($, I/I) - 如果栈顶为I且没有输入，则不做任何操作并移动到qf。

更新于：2021年1月7日

388 次浏览

开启你的职业生涯

通过完成课程获得认证

开始学习
广告