问题标签 [regular-language]

我正在为我的计算理论课程复习一些笔记，我有点坚持展示以下陈述，我希望有人可以帮助我解释:)

设 A 为正则语言。语言 B = {ab | a 存在于 A 而 b 不存在于 A*} 为什么 B 是常规语言？

有些观点对我来说是显而易见的。如果 b 只是一个常量字符串，这是微不足道的。由于我们知道 a 在 A 中并且 b 是一个字符串，因此常规语言在联合下是封闭的，因此联合接受这两个字符串的语言显然是常规的。但是，我不确定 b 是恒定的。也许是这样，如果是这样，那么这不是一个真正的问题。我很难理解它。谢谢！

大多数 UNIX 正则表达式除了通常的 , 之外，还有**一个+反斜杠?*运算符，其中\1,\2,...匹配最后括号中的任何内容，例如*L=(a*)b\1*匹配（非正则）语言*a^n b a^n*。

一方面，这似乎非常强大，因为您可以创建(a*)b\1b\1以匹配*a^n b a^n b a^n*堆栈自动机甚至无法识别的语言。另一方面，我很确定*a^n b^n*不能这样表达。

我有两个问题：

1. 有没有关于这个语言家族的文献（UNIX-y 常规）。特别是，这些引理是否有一个版本？
2. 有人可以证明或反驳*a^n b^n*不能以这种方式表达的事情吗？

如果给你一种语言，你如何判断它是正规的、CF 但不是正规的，还是短语结构而不是 CF？有没有解决这个问题的好方法？我可以随意尝试制作 FA 或 PDA，但我觉得有更好的方法来做。

经典例子：

L = { a^nb^nc^n | n >= 0 }

从哪里开始？谢谢。

我已经尝试并烧毁了我的大脑来理解离散数学及其应用（Rosen）中的正则语言的定义，但没有达到理解为什么定义在这本书中这样的目标。在第（789）页，我重新定义了定义：

类型 3 语法定义为：

其中 w1 是非终结符，而 w2 的形式为：

其中 B 是非终结符，a 是终结符。一个特殊情况是 w1 是起始符号而 w2 是 lambda（空字符串）：

我找不到答案的两个问题。首先，为什么w2不能采用Ba的形式。其次，为什么lambda只允许用于起始符号。书中指出，常规语言相当于有限状态自动机，我们可以很容易地看到，我们可以为这两种情况构建 FSA。我查看了其他资源，这些资源中不存在这些限制。

是否可以仅使用正则表达式来检测给定字符串是否是有效的正则表达式？

假设我有一些字符串，它们可能是也可能不是有效的正则表达式。我想要一个正则表达式匹配那些对应于有效正则表达式的字符串。那可能吗？或者我是否使用了一些更高级别的语法（即上下文无关语言）来检测这一点？如果我使用一些扩展版本的正则表达式，比如 Perl 正则表达式，它会影响吗？

如果可能的话，匹配正则表达式的正则表达式是什么？

我正在尝试使用 Ragel 来实现一个简单的 yes/no fsm。不幸的是，语言规范由大约一千个正则表达式的联合组成，其中大多数运算符出现一次或多次。因此，可能的状态数量激增，似乎不可能使用 Ragel 为我的语言生成 fsm。有没有可以做我需要的工具，或者我应该交换方法？我需要比依次检查每个正则表达式的输入字符串更好的东西。我可以将一千个正则表达式切成约 50 个的块，并为每个块生成一个 fsm，并对所有机器运行每个输入字符串，但是如果有一个工具可以在没有这种 hack 的情况下处理这种工作，我会很高兴听到它。

谢谢！

我为我的原始英语提前道歉；我会尽力避免语法错误等。

两周前，我决定更新我对 Scheme（及其启示）的知识，同时实施我手头上的一些数学材料，特别是我参加的自动机理论和计算课程中的常规语言。

到目前为止，我一直将字母表表示为符号列表，而不是

1. 字符列表，因为我想要可变大小的字母。
2. 字符串列表，因为我觉得那有点不雅。

我没有经验，想知道您对这个特定选择的看法。符号是为某种特定类型的任务保留的，因此我是否在滥用它们？非常感谢对此的任何评论，因为我正在寻求指导。

在更远的范围内，还有时间在一个无限的字母表上实现所有可能单词的集合。我正在考虑通过允许的最大单词大小来限制集合。再说一次，这是一个好习惯还是我应该转而选择流？我觉得流会是一种更好的方法，但我还没有学会它们，所以我真的不知道使用它们的含义。

无论如何，欢迎任何建议或评论。我非常感谢您花时间阅读我的疑问。周末愉快！

为包含或不包含 aa 和 bb 作为子字符串的字母 {a,b} 的字符串集给出 FA。这意味着 FA 接受所有没有 aa 和 bb 的字符串作为子字符串。如果我错了，请纠正我并给我一些提示。谢谢大家。:D

在阅读了 RE/NFA 和 DFA 之后，似乎使用 RE 而不是蛮力 O(mn) 查找，在字符串中查找子字符串实际上可能会更快。我的理由是 DFA 实际上会保持状态并避免多次处理“干草堆”中的每个字符。因此，如果使用正则表达式，在长字符串中的搜索实际上可能会快得多。

当然，这仅对从 NFA 转换为 DFA 的 RE 匹配器有效。

在使用 RE 而不是蛮力匹配器时，有没有人在现实生活中体验过更好的字符串匹配性能？

大多数语言都允许固定长度或有限长度的后视。一个值得注意的例外是 .NET，它允许使用 * 运算符。

但是，.NET 正则表达式已经可以使用命名捕获识别平衡括号，这不是常规语言。正则表达式在后视中是否仍然是带有 * 的常规表达式？对 * 以外的子表达式的扩展答案（例如，额外的环视！）也将不胜感激。

tl;dr：正则表达式是否与 * 保持一致？