问题标签 [automata-theory]

Σ={ a, b, c, d } L={ x ∈ Σ* | x 不以“bab”开头或结尾}

应该接受的例子：

• 亚贝巴
• ABAC
• bbabb
• 巴巴
• 抗体
• 巴
• 啊啊啊
• ε

应该拒绝的例子：

• 粑粑
• 爸爸
• 巴布克
• cbab
• 阿巴布

我尝试了几次，到目前为止得到了这个：

我的 dfa 的主要问题是它接受“bbab”

谢谢你。

我正在尝试开发一个在 Java 中执行非确定性有限自动机的模拟。第一个命令行参数是定义机器的文本文件。第二个参数是输入字符串。如果它接受字符串，它会打印到标准输出“accept”，然后是它可以结束的接受状态列表。如果它拒绝，它输出“reject”，然后是所有可能的结束状态的列表。

例如，文本：

看起来像：

输入字符串为 10 将输出

输入字符串 000 将输出

我需要关于使用什么数据结构的建议。我考虑过使用哈希图和集合，但我不确定。

我们知道如果 A 是有限的或在与自然数的一对一映射中，集合 A 是可数的。

假设 ALPH 是任意有限字母表。

我总结一下我的推论：

a) ALPH 上的每种任意语言都是可数的。（我认为这是真的）

b) 来自 ALPH 的所有语言的集合都是可数的。（我认为这是错误的）

c) 对于 ALPH 上的每种任意语言，我们都有一个生成形式语法。（我认为这是错误的）

d) 可以由形式文法生成的 ALPH 上的每种任意语言都是递归的。（我认为这是真的）

任何人都可以帮助我，也许纠正我？

我读了一些关于自动机课程的笔记。我看到了这个说明，以下都是一样的。但我认为 L(g) 不等于 NFA 和正则表达式。任何人都可以帮助我定义这些数字的语言（nfa、正则表达式和语法）：

所以在上面的例子中，事情是相当简单的，你只需找到可以为空的符号，消除 ε，并构造一个新的产生式，它可以在没有空字符串的情况下完成工作，我们得到这个..

然后我遇到了这个例子

现在A产生B，B可以清楚地产生一个空字符串。是否意味着 A 可以为空是 S 并且如果它不直接产生一个可以为空的终端，我不知道是否有可能使终端无效？

因此，我正在为一项关于下推自动机和无上下文语言的测试而学习，我被困在这个结构上。

除了我将在下面解释的一部分外，我让这个自动机的每一部分都完美地工作。

它需要识别的语言是：{ x#y#z#w | x, y, z, w in {0, 1}+ 其中 x ≠ w 和 y ≠ z }。

所以我遇到的问题是将 Xi 与 Wi 进行比较，因为在自动机处理 W 时，Wi 的元素是未知的，就像我设计的那样。

如果我存储 X 的内容，当需要弹出并将每个元素与 W 的元素进行比较时，它们将以相反的顺序弹出，因此认为 000111 和 111000 是相同的字符串，PDA 会拒绝，什么时候应该明确接受（它们是不同的字符串）。这只是一个例子，这也会导致其他输入被错误地分析。

如果有办法将 X 的内容以相反的顺序推入堆栈，它们将以原始形式弹出，使我能够正确比较字符串的内容。

如果有办法在正常推送后反转堆栈的内容，这也将使我得出解决方案。

任何帮助将不胜感激。谢谢。

我正在尝试将以下 CFG 转换为下推自动机：

我不太确定如何解决这个问题，或者一般来说 CFG->PDA 的问题。

在使用 PDA 定义 CFG 或类型 2 语法的转换时，我们需要初始堆栈符号，主要由 Zo 表示。我的疑问是为什么我们需要它，因为最终我们将完全清空堆栈......？？

我在封闭联合运算定理下学习常规语言。我得到了 Q,F,q _o，但我对得到 delta δ 感到困惑。请用示例特别解释增量部分。

我们是否需要先将上下文无关语法转换为乔姆斯基范式才能将其转换为格雷巴赫范式？