问题标签 [finite-automata]

下面的正则表达式等价是真的吗？为什么或者为什么不？

(ab)* u (aba)* = (ab u aba)*

*=克莱恩星

u=并集（集合论）

(ab u aab u aba)*

我做到了，但我想要一些关于其正确性的反馈：

如果正确：我们可以进一步简化 (ab u aab u aba)* 吗？

如果没有：我错过了什么？

编辑：似乎我缺少从所有 3 个最终状态回到初始状态的电子转换，我需要一个初始和最终状态的新状态，它将在电子转换时进入旧的初始状态。（克莱恩星规则）。

PS我们也可以简化(a u b)*aabab和(a u b)*a(a u b)(a u b)(a u b)(a u b)。

我之所以问是因为如果没有办法简化/最小化，那将是一个非常长的 DFA ......

显而易见的选择是耗尽所有可能的输入。我想我做到了。但我不太确定它是否有效，并且我没有违反任何非确定性有限自动机的规则。

我的 NFA 由以下给出：(ab u aab u aba)*下面是我的图表。

我错过了什么吗？

我想它会是（E0 * 0 * EUE1 * E）？其中 E 是我的字母表的集合，至少有 2 个 0 和至少 1 个 1

换句话说，我为什么要学习它？我什么时候要说...哦，我需要知道下推自动机或图灵机。

我看不到材料的应用。谢谢

感觉就像我被困住了，我的朋友们。有人可以解释我从“功能算法设计的珍珠”第 11 章（“不是最大段总和”）中挑选方程。

这是问题（有点简化）让我们有一些具有给定转换的状态：

现在，让我们定义pick：

作者声称以下七个等式成立：

有人可以用简单的话解释我，为什么这些方程式是正确的，我们如何证明一个明显的证据？我觉得我几乎理解了 S 方程，但总的来说这仍然是难以捉摸的。

我的 C 有点不稳定，但我查看了 python 的源代码，看起来 python 的大部分re模块都是由状态机实现的。这并不奇怪，因为正则表达式可以简化为确定性有限状态机。

我想其他正则表达式实现是相似的。但是根据教科书的定义，很少有现代正则表达式实现是常规的。那么他们如何解释不规则性，比如反向引用？

我正在实现自己的 fsm 来解析文件。我是 fsm 模式的新手，所以试图了解它。

我的 fsm 类采用正在解析的文件流以及当前状态和所有接受状态的集合。

现在我对几件事感到困惑。

1. fsm 如何通过状态移动并跟踪到目前为止已解析的内容？

2. 状态对象应该存储哪些信息？现在他们有一个匹配的模式，看看 fsm 是否可以移动到这个状态。

例子：

要解析的文件：

所以我有一个人开始，年龄，位置和结束人的状态。每个状态对象都有一个模式。（正则表达式）检查给定的行是否被他们接受。

但是我被困在使用 fsm 解析这个文件时如何构造一个 Person 对象？

我想我接近这个答案，但仍然要确认我们是否可以创建一个可以进行实数计算并给出准确结果的图灵机（至少在原则上）？**例如找到整数的平方根。（其输出将是一个实数）我认为我们不能开发这种机器的逻辑是，实数是不可数无限的，对于不可数无限的语言，我们无法创建图灵机。

DFA 中接受具有“1”作为右起第 5 个符号的字符串所需的最少状态数是多少？字符串在字母表 {0,1} 上定义。