问题标签 [automata-theory]

我想要在定义 r 和 r 的 DFA 时找到 r* 的 DFA 的示例。又该如何思考？我读了一本教科书，但我没有清楚地理解。谢谢你。

让语言 L_n 具有字符集 Sigma = {a_1, ..., a_n}。L_n 恰好有那些包含某些字符奇数次的单词。等效地，如果 L_n^i 是每个单词包含奇数个 a_i 的语言，则 L_n = L_n^1 union ...union L_n^n。

我已经生成了一个接受 L_n 的 NFA 和一个 2^n 状态的 DFA，它也可以。

我现在需要证明这是接受这种语言的最小 DFA。我得到提示，假设有一个接受 L_n 的 k < 2^n 个状态的 DFA，然后表明Sigma^* 中有一些字符串u,v ，其中u包含a和奇数次，v包含它是偶数次，并且 DFA 必须在同一状态下终止。

我一直试图将 2^n 作为一个强有力的提示，比如可能考虑所有长度为 n 的字符串，但其中有 n^n 个。也许考虑所有长度为 n 的字符串只使用字符a,b。由于有 k < 2^n 个状态，因此必须将一些像这样的两个字符串发送到相同的状态。这组中被拒绝的字符串是具有偶数a和b的字符串，但我无法知道这些实例的两个这样的实例是否进入相同的状态，或者如果它们确实如此，那会有什么关系。

也许考虑所有字符串的选择，其中 a_1 出现一次或 0 次， a_2 出现一次或 0 次，等等。这些有 2^n 选择，因此其中一些必须进入相同状态。唯一不在该语言中的字符串是空字符串。我还是被困住了。

嗨，我有一个关于定时自动机的理论问题，我想知道是否有人已经给出了答案，因为这对我的研究很有用。所以我的问题如下：

假设您有一个定时自动机，它的接受状态为 q_f（没有后继），并且您知道配置 (q,delta) 的所有轨迹（对于自动机的位置 q 和时钟评估增量）总是终止，即它们导致q_f。这是否意味着存在具有最大长度的迹线？？？（例如（q，delta）的计算树具有有限深度）

给出一个生成语言的上下文无关文法 H

提示：m 不能为 0，因为在这种情况下 2m = m。m 不能为 1，因为在那种情况下 2 > n > 1，这样的自然数 n 不存在。所以语言 M 中最短的字符串是 aabbb。对于较长的字符串，需要确保 bs 的个数 n 和 as 的个数 m 满足 2m > n > m。

考虑语法：E-> E+E|EE|E*E|E/E|(E)|id

我已经尝试了至少 5 个小时来解决这个问题，但失败了。请告诉我，

• 解决这个问题的想法是什么？

• 如何实施？

我有以下棋盘：

每个方格都是一个状态。初始状态是“a”。

给定他想要移动的方块颜色的用户输入，程序需要根据该输入找到所有可能的路线。

例如：如果输入是 W（白色），我们从“a”到“e”。如果输入是 R（红色），我们同时从“a”到“b”和“d”。另一个更复杂的例子：如果输入是 WR，我们从 "a" 到 "e" 对于 W，然后从 "e" 到 "b"、"d"、"f" 和 "h" 对于 R .

我有以下python程序：

开关是一个字典，其中包含板的每个状态（正方形）的单独功能。这些函数返回一个状态字符串，您可以根据某些输入移动到这些状态。

例如对于状态 a：

chess 函数以这种方式打印包含状态的矩阵： 对于输入 WR，它给出以下输出：

到目前为止一切顺利，但我需要将所有路线分开。对于相同的输入，我应该有以下输出：

任何想法如何从矩阵中得到它？

我想制作一个图灵机，它接受长度为 3 的 1 的字符串。111、111111111、111111111111111111111111111，依此类推。但我无法为此制定算法。到目前为止，我能够制造可以接受长度为 3 的倍数的机器。请帮助我

由于递归可枚举语法不受限制，是否可以在 LHS 中有一个或多个终端（即没有非终端）的产生式？

我试图证明语言 L = {a^n! | n>=0} 不是使用泵引理的上下文无关的。但我被困在如何划分 uvxyz 本身。由于它只有一个符号，我觉得它非常棘手。

我正在尝试学习如何解决以下练习。我不明白如何开始，它是压倒性的。我确实了解 DFA、NFA 以及如何将 DFA 转换为 NFA。我也理解正式的符号。

这不是家庭作业，只是为了学习。我确实有解决方案，但我也无法理解它..

如果有人可以 ELI5 练习那将是惊人的，解决此类练习的示例（有适当的解释）也会很棒，我还没有在网上找到类似的练习。

鉴于：

• 字母Σ

• 符号 c ∈ Σ

• 正则语言 L over Σ

语言 Lc = {uv | ucv ∈ L}

令 D = (Q, Σ, , q0, F) 为ℒ(D)=L 的 DFA。

展示如何使用 D 的副本构造 NFA N，使得 ℒ(N)=Lc。提供 N 的正式定义。