问题标签 [finite-automata]

什么是 R-平凡语言？即定义是什么？

什么是 R-平凡幺半群？

背景：正式语言。Afaik，R-trivial 语言是无星语言的子集。

我主要有形式语言和自动机理论的背景，但对句法幺半群表征不太了解。所以最好用这种语言的一个小例子来给出一个基本的定义。

（为了支持多个 QA 站点，因为我不想让任何 QA 站点留在后面，也不想让那个问题也出现在那里，我还在这些其他站点上发布了这个问题：cstheory.stackexchange.com，math .stackexchange.com , mathoverflow.net . 一般来说，我反对交叉发布，但在这种情况下，因为它们都有相同的目标，即成为特定领域问题的完整参考，交叉发布问题是最好的你可以做。）

我正在尝试制作一个简单的 Lexer 来了解它们是如何工作的。我正在尝试找出一个可以捕获任何类型的打开 HTML 标记的良好 POSIX 字符串。我做了一个几乎可以工作但在更复杂的标签（如元标签等）上失败了。到目前为止，这就是我所拥有的：

这个 POSIX 字符串捕获了很多标签，但错过了一些像元标签和 DOC 标签。这是一个失败的标签：

任何帮助将非常感激。我知道这可能不是制作 Lexer 的最佳方式，但这只是为了帮助我了解 Regex 的工作原理。

有没有人对构造两个给定 DFA 的并集的算法有简单的描述？例如，假设我们有两个超过 {0,1} 的 DFA，其中

我有一个结果转换表，将联合显示为：

我的讲义中有一个图形解决方案，但想看看其他人会如何描述它。由此，我可以看到，我们基本上使用它们的状态值“乘”这两个原始表以产生更大的转换表。因此可以从结果表中得出 DFA。这听起来是否正确，这是否适用于所有 DFA 案例，还是我遗漏了什么？

有人能比我简洁地向 SO 社区描述 NFA 到 DFA 的转换算法吗？（最好是 500 字或更少。）我看到的图表和讲座只会混淆我以为我曾经知道的东西。我最有信心从状态图中生成初始 NFA 转换表，但在那之后，我失去了 epsilons 和子集中的 DFA。

1) 在转换（delta）表中，哪一列代表新的 DFA 状态？它是生成状态的第一列吗？

2) 在我下面示例的第 {2,3} 行第 0 列中，就 NFA 的状态图而言，{2,3} 是什么意思？（对不起，我必须在图片中思考。）我认为这将是 DFA 中的“输入 0 环回”？

3) 关于从表到 DFA 或识别结果 DFA 的接受状态的任何简单“经验法则”？

有限自治

编辑：这是上面的点格式表格，欢呼Regexident。

在这里呈现形式：

注意：该表缺少有关州接受度的任何信息，因此图表也是如此。

我有一个可以通过迭代解决的问题，但我想知道是否有使用正则表达式的更优雅的解决方案和split()

我有一个字符串（excel放在剪贴板上），本质上是逗号分隔的。需要注意的是，当单元格值包含逗号时，整个单元格会用引号括起来（大概是为了转义该字符串中的逗号）。示例字符串如下：

现在，我想优雅地将此字符串拆分为单个单元格，但问题是我不能使用以逗号作为分隔符的正常拆分表达式，因为它会拆分值中包含逗号的单元格。另一种看待这个问题的方法是，如果逗号前面有偶数个引号，我只能用逗号分割。

这很容易用循环解决，但我想知道是否有一个正则表达式.split 函数能够捕获这个逻辑。为了解决这个问题，我为逻辑构造了确定性有限自动机 (DFA)。

现在的问题被简化为以下问题：有没有办法拆分这个字符串，以便在 DFA 中每次达到最终状态（此处为状态 4）时产生一个新的数组元素（对应于 /s）？

我正在尝试从有限自动机构造一个正则表达式，但发现我自己完全被这个所困扰。要使用的正则表达式是这样的：

? = 0 或 1
* = 0 或更多
+= 1 或更多
| = 或
_ = 空字符串
@ = 空集
() = 括号

据我了解，字符串必须是以“a*”结尾的“b*”或以“a+bb+”结尾
我现在拥有的是((b*(a+(bb))*)*) ，但这并没有考虑到以“a”结尾的字符串。

如前所述，我 100% 坚持这一点，只是无法理解我应该如何处理这个问题。

图片：http: //img593.imageshack.us/img593/2563/28438387.jpg

代码：
自动机
FA 的类型

州
q1
q2
q3
q4

字母
a
b

初始状态
q3

最终状态
q3
q4

过渡
q1 a q2
q1 b q3
q2 a q2
q2 b q2
q3 a q4
q3 b q3
q4 a q4
q4 b q1

任何解决方案或提示表示赞赏！

有人可以告诉我什么是有限状态传感器吗？

我已经阅读了维基百科的文章，但什么都不懂。

我正在阅读 Peter Linz 的一本名为“形式语言和自动机简介”的书。在它的一个问题中，它要求我，"Design an acceptor for integers in a programming language C"有人可以告诉我如何获得这个答案。任何帮助将不胜感激

用字母 { a }定义语言L如下

L = { 一个^nk | k > 0 ; n 是一个正整数常数 }

DFA 中识别L所需的状态数是多少？

在我看来它应该是 k+1 但我不确定。

我正在开发一个将非确定性有限状态自动机 (NFA) 转换为确定性有限状态自动机 (DFA) 的程序。为此，我必须计算 NFA 中每个具有 epsilon 转换的状态的 epsilon 闭包。我已经想出了一种方法来做到这一点，但我总是认为我首先想到的通常是做某事效率最低的方法。

这是我如何计算简单的 epsilon 闭包的示例：

转换函数的输入字符串：格式为 startState，symbol = endState

EPS 是一个 epsilon 转换

1，每股收益 = 2

结果在新状态 { 12 }

现在显然这是一个非常简单的例子。我需要能够从任意数量的状态计算任意数量的 epsilon 转换。为此，我的解决方案是一个递归函数，它通过查看它有一个 epsilon 转换到的状态来计算给定状态的 epsilon 闭包。如果该状态具有（一个）epsilon 转换，则在 for 循环中递归调用该函数，以获取尽可能多的 epsilon 转换。这将完成工作，但可能不是最快的方法。所以我的问题是：在 Java 中计算 epsilon 闭包的最快方法是什么？