问题标签 [regular-language]

我在解决问题时遇到了问题：- 这是一个作业，我解决了，但它似乎太长太模糊了，请任何人帮助我......

具有偶数个 a 和奇数个 b 的字符串的正则表达式，其中字符集={a,b}。

我觉得在这里发布如此简单的问题就像一个白痴，但这个网站的知识库真是太棒了。感谢您的理解。

关于寻找正则表达式的最小泵送长度（关于正则语言的泵送引理）的问题：

正则表达式 R = 1011（在字母表 {0,1} 上）

不是这个字符串 ε（空字符串）和 1011 的唯一匹配项吗？

编辑-我一直在盯着太多的 kleene 明星。空字符串 ε 不是这种语言。

正则语言的属性表明，如果一种语言可以用有限自动机（或正则表达式）表示，那么它就是正则的，当然这个语言也可以用两者来表示。（而且这个问题显然让我相信语言是正常的）

但另一方面，抽水引理（非正式地）指出，所有常规语言都具有抽水长度，因此至少该长度的所有字符串都可以拆分为 xyz，其中 y 可以重复而不会影响结果。ε 不能按定义泵送，并且 1011 不能泵送（我不认为，这是问题）因为没有其他字符串匹配它，因此删除或添加 y 的实例将导致字符串不被接受/匹配。

我的逻辑错误在哪里？

第二次编辑-任何 p>4 的答案是否可以通过将 x 或 y 或 z 设置为 φ （空集）来抽取语言，当与任何东西连接时会导致空集？

顾名思义，我们可能认为正则表达式只能匹配正则语言。但是我们在实践中使用的正则表达式包含一些我不确定是否可以用它们的理论对应物来实现的东西。例如，您将如何模拟反向引用？那么问题来了：我们在实践中使用的正则表达式的理论威力是什么？你能想出一个匹配的方法{(a^n)(b^n)|n>=0}吗？怎么样{(a^n)(b^n)(c^n)|n>=0}？

我在这里看到一些评论提到现代正则表达式超出了常规语言可以表示的范围。这是怎么回事？

现代正则表达式的哪些特征不是正则的？例子会很有帮助。

我被这个练习问题难住了（不是为了分数）：

{w 是 {a,b}* 的一个元素：a 的个数是偶数，b 的个数是偶数 }

我似乎无法弄清楚这一点。在这种情况下，0 被认为是偶数。一些可接受的字符串：{}、{aa}、{bb}、{aabb}、{abab}、{bbaa}、{babaabba} 等

我做过类似的例子，其中 a 必须是前缀，答案是：(aa) (bb) 但在这种情况下，它们可以按任何顺序排列。

可以使用 Kleene 星 (*)、并集 (U)、相交 (&) 和串联。

编辑：这个也有问题

{w 是 {0,1}* 的一个元素：w = 1^r 0 1^s 0 对于某些 r,s >= 1}

我正在研究会员算法，我正在研究这个特定的问题，它说以下内容：

展示一个算法，给定任何常规语言 L，确定 L = L*

所以，我的第一个想法是，我们有 L*，它是 L 的 Kleene 星，并且要确定 L = L*，我们不能只说因为 L 是规则的，我们知道 L* 是根据定义说明常规语言家族在星闭合下是闭合的。因此 L 将始终等于 L*？

我觉得肯定还有很多东西，我可能缺少一些东西。任何帮助，将不胜感激。再次感谢。

通常在我们的工作中，我们在捕获或匹配操作中使用正则表达式。

但是，可以使用正则表达式（至少手动）来生成与正则表达式匹配的合法句子。当然，有些正则表达式可以匹配无限长的句子，例如表达式.+。

我有一个问题可以通过使用正则表达式句子生成算法来解决。

在伪代码中，它会像这样运行：

什么算法会为我执行此操作？

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

什么是 R-平凡幺半群？

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

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

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

即，我得到一个单词列表，我想从匹配至少所有单词（但可能更多）的单词中构造一个简单的正则表达式。

我想有一个算法。即该算法的输入是单词列表，输出是正则表达式。显然，会有一些限制。就像正则表达式应该匹配无限数量的单词时总是匹配更多的单词，而我只给它有限数量的单词。或者我需要一些更紧凑的输入表示。或者我也在考虑给我一些正则表达式作为输入和一个额外的单词列表，我想得到一个正则表达式，它将所有它们匹配在一起（也许更多）。无论如何，它应该尝试构造一个尽可能简单的正则表达式。

有哪些技术可以做到这一点？

我被误解了。我知道正则表达式背后的一般原则。我知道它是什么。在大多数情况下，我可以很容易地手动为某种语言提供正则表达式。但我正在寻找能够做到这一点的算法。

再次表述有点不同：

令 L 为常规语言。令 M_n 是具有 n 个元素的 L 的有限子集。令 M_n 是 M_(n+1) 的子集。

我想要一个算法 LRE，它可以获取一组有限的单词并输出一个正则表达式。我想拥有财产：

lim_n->无穷大 ​​| 差异（LRE（M_n），L）| = 0

Pumping Lemma 用于证明语言不规则。但是如何
证明一种语言是正则的呢？尤其是，

是否有任何技巧或一般程序来解决此类问题？