问题标签 [automata]

我正在尝试编写一个最小化转换图的程序（它基本上结合了具有相似数字的状态）。基本上，该算法是首先找到具有相同 'a' 和 'b' 输入的状态，将它们组合起来，将它们从 'leftovers' 列表中删除，然后找到具有 'a' 或 'b' 的状态并将它们组合起来。

这是一个例子：

我面临的问题是知道如何/如何处理数组，因为可能存在任意数量的组合，具体取决于给定转换图中的状态数量。关于如何编码的任何想法或关于如何处理一切的任何建议？

干杯

我有一个 DFA，但我不知道它是否接受状态。我只知道它接受的正则表达式。我试图找出它是否是接受状态，所以我查看了 DFA 的每个状态，我想将接受正则表达式与当前状态生成的单词进行比较。

所以我正在寻找可以将这个词与正则表达式进行比较并告诉我它是否匹配的东西，这样我就可以将 DFA 的这个状态标记为接受状态，然后进入另一个状态。我试图实现一些算法，但事实证明这对我来说是一个相当复杂的问题。你能给我建议吗？谢谢！

字母：{a,b,c}

正则表达式示例：ab.(a|c)*

找不到任何肯定的东西。具有任何 epsilon 转换的 NFA 是 epsilon-NFA 吗？谢谢。

我试图以多种方式解决这个问题，并在几个地方都没有答案。问题如下：

[问题]
给定两种常规语言（可以称为有限描述语言，idk）L1和L2，我们定义一种新语言如下：

我应该用来证明L is regular，但是我有以下限制：

• 我必须使用 Equivalence 类，别无他法

• 我不能使用Rank(L)，如显示对等价类数量的限制，而是必须显示它们

• 我可以使用所有常规语言都拥有的闭包属性

我并不期待一个完整的证明（尽管这将不胜感激），而是对如何去做这样的事情的解释。
提前致谢。

考虑 DFA：

δ(A,01) 等于多少？ 选项：

正确答案是选项 B），但我不明白如何。请有人向我解释解决它的步骤，以及一般来说，我们如何解决任何 DFA 和任何过渡的问题？

谢谢。

还是 C# 的新手，所以要友好:)

如何将这些产生式存储在数组中或以表格形式存储在列表中，如下面的 c# 中。以上产品是从文件中读取的。

我正在尝试理解上下文相关的语法，并且我理解为什么语言喜欢

1. {ww | w 是一个字符串}
2. {一个ⁿ b ⁿ c ⁿ | a,b,c 是符号}

不是上下文无关的，但我想知道类似于无类型 lambda 演算的语言是否对上下文敏感。我想看一个简单但非玩具的示例（我考虑上面的玩具示例），上下文相关语法的示例，对于某些生产规则，例如，判断是否有一些符号字符串当前在范围内（例如，在生成函数体时）。上下文相关的语法是否足够强大，可以使未定义/未声明/未绑定的变量成为语法（而不是语义）错误？

这是我画的DFA-

这是正确的吗？
我很困惑，因为q4状态2对于违反规则的相同输入符号有不同的转换DFA，但我想不出任何其他解决方案。

我需要一些帮助来确定给定的语言是常规的、上下文无关的还是非上下文无关的。答案中简短的非正式解释就足够了，因此无需使用抽水引理。

可以说我有以下语言：

这是我的解决方案：

可以为 L2 构造一个 DFA，因为 L2 不需要无限的内存，所以 L2 是规则的。对于 L3 的推理与上述相同。对于 L4，我们可以构造一个根本不接受“abc”的 DFA，因此是常规的。

L1 是正则的，因为正则语言在 ∩ 下是封闭的。

对于 L2，我们可以将语言分为：

我们知道可以为 L3 构造 DFA，因此 L3 是规则的。L4 是上下文无关的，因为我们可以构建一个 PDA，其中堆栈用于计算 a:s 和 b:s 的数量。

L2 因此是上下文无关的，因为常规语言和上下文无关语言的 ∩ 导致上下文无关语言。

对于 L3，我们可以看到它是非上下文无关的，因为我们被限制为 1 个堆栈，并且要进行超过 1 个比较，我们需要更多的堆栈。

是我的推理权利吗？我很快就要考试了，需要知道我是否有这个想法。

提前致谢

我目前有一个（自然语言）语料库，这些是已经采取的步骤：

1. 将语料拼接成一个大文件后生成符号表：

2. 给定此符号表，将语料库转换为二进制 FST 存档 (FAR)：

我想取 FAR 中所有 FST 的并集，并计算从起始状态到最终状态的最高权重路径。要从 shell 进行测试，这就是我所做的：

但我一直遇到以下错误：

警告：CompatSymbols：第一个符号表存在但第二个缺失

错误：联合：第一个参数的输入/输出符号表与第二个参数的输入/输出符号表不匹配

当然，如果我尝试运行二进制操作而不首先对 FST 进行排序，则此错误仍然存​​在。

我认为我没有正确排序 FST，或者......我完全误解了如何使用符号表。知道为什么联合（或任何其他二进制操作，就此而言）会这样失败吗？