问题标签 [finite-state-automaton]

这种语言是正规的吗？我找不到解决方案，而且我对它的感觉很复杂，顺便说一句，我最近两周才这样做。

众所周知，“有限状态自动机”的定义是：

然后我们将这个有限状态自动机描述为：

那么我们就有了结论：

问题是：如果自动机第一次读取的字符串是'2'，而不是接受一个空字符串，那不属于这个自动机的字母（0,1）怎么办。这个自动机还会去接受状态吗？

图片引自《计算理论导论》一书

《计算理论导论》一书中“pumping lemma”的证明：

抽水引理：如果 A 是正则语言，则有一个数 p（抽水长度），其中如果 s 是 A 中长度至少为 p 的任何字符串，则 s 可分为三段，s = xyz，满足以下条件：

1. 对于每个 i ≥ 0，xyiz ∈ A，
2. |是| > 0，并且
3. |xy| ≤ p

令 M = (Q, Σ, δ, q1, F) 是识别 A 的 DFA。我们将泵送长度 p 指定为 M 的状态数。我们证明 A 中长度至少为 p 的任何字符串 s 可能被分成三块xyz，满足我们的三个条件。如果 A 中没有长度至少为 p 的字符串怎么办？那么我们的任务就更容易了，因为这个定理变得空洞地正确：显然，如果没有任何这样的字符串，这三个条件对于所有长度至少为 p 的字符串都成立。

问题：粗体引用部分，我认为这是错误的。因为如果 A 中没有长度至少为 p 的字符串，那么它显然不是常规语言。

从< Introduction_to_the_Theory_of_Computation >抽取引理"

问题：我们可以将第一个条件修改为，for each i > 0而不是for each i ≥ 0？

我需要这个解决方案的帮助，因为我刚刚开始研究有限状态自动化并且无法帮助自己解决这个问题。

这个问题是否意味着我必须提供输入 1101 1101 如果是这样，如果位字符串不是以两个 D 开头，如何显示要进入的另一个状态

如上所述，我有一个转换图，但我不知道如何找到它的语言，在我看来有很多可能性，但我一定是误解了。我的理解是，任何从初始状态到最终状态的词都被接受。当然，有很多不同的方法可以实现这一目标。阿布，阿布，阿布，阿巴布。据我了解，一种语言是所有可能单词的集合，但是如果有大量可能的单词，您如何找到该语言？我是大学一年级的学生，这是我家庭作业的一部分，但我不只是想让你为我做这件事，我想理解它——如果这没有意义/在错误的地方我提前道歉，谢谢。这是我的图表

在一次讲座中，据说这个 NFA 接受以两个零或输入 = 0 结尾的输入：https ://ibb.co/9Wt0j7J 。字母表是 {0,1}

但是如果输入是 001，我们会在某些路径上也最终处于接受状态 (z2)，但是在读取最后一个字符时不可能回到另一个状态。这意味着接受了错误的输入。所以，我的问题是：在不改变任何东西的情况下，NFA 真的构造正确吗？如果是，为什么？如果没有其他箭头指向另一个状态，我是否可以假设我们进入“空（不可见）状态（错误状态而没有明确提及）”或类似的状态？

我正在尝试为项目操作有限状态传感器。但是，在构建 FST 时，我需要每个输出符号都是来自输入符号的任意长字符序列，这些字符只是来自相关文本语料库的单个唯一字符。此外，我需要统一表示这些任意长的序列，以便每个组合的表示具有相同的长度。当然，对于任意长度，可能的最长组合具有无限长度，因此让我们假设没有组合可以比相关语料库中最长的文档更长。

换句话说，给定一个input_vocabularyof ['a', 'b', 'c']，一个output_vocabularyof['a', 'ab', 'acb', 'abcb']需要每个都表示为某个长度为 4 的向量，每个向量中的每个项目都是来自 的项目input_vocabulary。我唯一的想法是使用填充向量来做到这一点，例如，对于这个例子，[ [0, 3, 3, 3], [0, 1, 3, 3], [0, 2, 1, 3], [0, 1, 2, 1] ]，其中3是一个填充标记，但我对此很陌生，所以任何帮助将不胜感激。

为了澄清，我想知道是否有办法在没有填充令牌的情况下做到这一点。

我有一个 Petri Net 模型，我想将它转换为 FSM。我考虑了 PN 的可达性图，RG 是否与 FSM 的可能表示同构？

先感谢您！

我正在尝试使用适用于 Python 的赫尔辛基有限状态技术 (HFST) 设置有限状态传感器。

我希望如果单词的第一个字符是“o”，则输出为“正”，并且如果在同一个单词中有字符，则使用正则表达式为每个字符输出空。
但我不只接受“o”。

到目前为止，我从 HFST 教程中得到了什么：