时间戳

首页 > 解决方案 > 我如何按照这个规则构建这个下推自动机

computer-science - 我如何按照这个规则构建这个下推自动机

问题描述

规则是：不能以字母a开头。它不能以字母 b 结束。它必须包含 b=ia=2i。字母表是a，b。我试过这样做清空堆栈。但不幸的是，我无法达到它。像这样的输入例如： bbaaaa 没问题，因为对于每个 b 输入，我都将其放入堆栈 2 a 并且 a 输入会删除堆栈。但是当输入是这样的时候：baaabbaaa can't follow that steps。有什么建议吗？

标签： computer-scienceautomatafinite-automatapushdown-automatonautomata-theory

解决方案

我的方法是这样的：

使初始状态接受（因为空字符串满足语言标准）并在 b 上进行到另一个状态的单个转换。作为此转换的一部分，将两个 b 压入堆栈。如果 PDA 在初始状态看到 a ，它将崩溃并拒绝。

我们转换到的另一个状态对应于刚刚看到的 b。因为我们的字符串不能以 b 结尾，所以这个状态不能接受。如果我们在这里看到另一个 b，我们可以循环回到这个状态，每次都向堆栈添加两个 b（如果堆栈顶部有 b）或者取消两个 a（如果有两个 a）或替换 a与 b （如果堆栈只有一个 a）。如果我们看到一个 a，我们必须进入一个新状态，我们应该从堆栈中弹出 ab（如果有 b）或压入另一个 a（如果 a 在顶部）。

第三个状态意味着我们最后一次看到了一个 a，所以如果我们在这里用空堆栈用完输入，我们应该接受。如果我们看到 a，我们可以留下并弹出 b（如果 b 在顶部）或 push a（如果 a 在顶部）。如果我们看到 b，我们应该返回第二个状态，并根据堆栈内容压入两个 b，弹出两个 a，或弹出 a 并压入 b。

我们的堆栈跟踪 PDA 必须看到以清除堆栈的附加符号的数量，如下所示：

  • 堆栈一次只能包含 a 或 b，永远不会同时包含
  • 如果我们已经看到 na 和 mb 并且 n = 2m，则堆栈将为空
  • 如果我们已经看到 na 和 mb 并且 n > 2m，堆栈中将有 n - 2m a
  • 如果我们看到 na 和 mb 并且 n < 2m，堆栈中将有 2m - nb

推荐阅读