问题标签 [automata-theory]

我被告知这个 NPDA 是错误的，但我不明白为什么，有人能发现这个错误吗？

谁能告诉我可以从正则表达式 (a+b)* 生成哪些字符串？能不能生成abbbb和ababab。?

任何帮助将不胜感激。

我想设计一个接受语言 L= {a^2b^2n: n>=1} 的图灵机：。a 方 b 方 (n)

我试图通过首先为长度为 4i 的字符串设计一个 NFA 来解决这个问题，因为它的形式是 0(mod 4)。

状态数 = 4，我刚刚添加了 2 个其他状态，本设计的每一端各一个，并在 0 上进行了转换，现在状态数 = 6。当我尝试检查时，我的解决方案是错误的。有人可以解释我哪里出错了吗？

随着科技的进步，工业已经朝着自动化和智能化的方向发展。在这方面，人工智能和机器学习发挥了至关重要的作用。自然语言处理（NLP）是计算机科学和语言学的一个领域，专注于处理自然语言的方法。那么，在自然语言处理中，Finite state machine [FSM] 和 Push down Automata 哪个更可靠、更高效？

我发现了正则表达式 (00+1)* 的逆同态的一个例子（在 'Hopcroft, Motwani, ullman' 书的第 131 页）。

如果 h(a)=01 和 h(b)=10，那么作者说给定正则表达式的逆同态是正则表达式 (ba)*。

但是 (00+1)* 语言中的字符串 00 和 1 不能用 (ba)* 语言中的任何字符串表示。

这个例子是错误的还是我想错了方向？

对于 LTL 公式FG p & FG q，我想嘲笑或拒绝它等同于 F (G p & Gq). 我认为根据分布规律，我们可以F(Gp&Gq)写成FG(p&q). 我们也可以说FG p & FG q = FG(p&q)吗？

我只是自动机领域的新手。看了很多文章，看了很多视频。我坚持了一些最初的话题。对其他人来说可能很容易。但是花了很多时间之后，我仍然无法理解它。主题是：字母表中的歧义

一个字母是 = {A, Aa, bab, d}，一个字符串是 s= AababA

并且作者说，这是模棱两可的字母，因为当计算机读取它时，它是从左到右读取的。在大写A之后，再有A是小a的前缀，会产生歧义。字母（符号）不应再次作为新字母的前缀。而且作者说。我们将以两种方式对其进行标记（AababA）：

• (Aa) (Bab) (A)
• (A) (阿巴) (A)

之后，第一个可以，第二个不可以，因为上面定义的字母不明确。

1. 以两种方式标记上述字符串的过程是什么？有什么具体规则吗？
2. 由于第二组，字母表如何模棱两可。
3. 如果由于A的前缀而无效，那怎么办？前缀在字母歧义中的作用是什么？
4. 如果我们不考虑前缀，只是简单地将两个字符串组与上面的字母匹配，那么我们可以很容易地判断，第二个不匹配上面的字母，那么为什么我们需要讨论那个前缀呢？

我希望，这个问题会被认为是重要的，所以这个答案将帮助我摆脱这种困惑。我将非常感激。

回文是自动机中的一种语言。但我无法理解以下段落。我计算了很多东西，并尽力估计，但我做不到。

回文长度：我们知道字符串的长度为 n，字母表中的符号数为 2，这表明长度为 2n 的回文数与长度为 n 的字符串一样多，即所需的回文数为 2 ^n。

令 S= {a, bb, bab, abaab} 是一个字母表。并且 kleene 闭合将是 S* 将所有可能的组合。

S* 中是否存在字符串 abaabbabbaab？

什么是分解以检查它是否在 S* 中的方法？我已经通过以下方式完成了可能的分解：

1. (abaab)(bab)(b)(a)(a)(b)
2. (abaab)(bab)(b)(aa)(b)
3. (abaab)(bab)(ba)(ab)
4. (abaab)(bab)(咩)(b)
5. (abaab)(bab)(b)(aab)

我们可以看到 (abaab)(bab) 是匹配的，但后面的部分不匹配 S* 中的意志组合。我已经以多种方式分解了后面的部分，但仍然不匹配。我想问那个，

• 这是对的吗？

• 这是分解（标记）字符串的正确方法吗？

• 所有分解对都正确吗？

• 这是检查字符串是否属于一种语言的正确方法吗？