问题标签 [regular-language]

我正在上自动机理论课，现在我们正在学习抽水引理。有一个练习题要求我们“设计一种语言 L，使得 L 和它的补码都没有无限的正则子集？” 但我不明白这个问题。什么是无限正则子集？我应该如何找到可以满足此要求的语言？

任何人都可以对这个问题有所了解吗？

谢谢！

本质上，我想知道是否可以用正则表达式替换特定的 XSD 架构。我知道 XML Schema 语言可以生成 XSD，其有效 XML 实例集可以是任何类型的语言（甚至是上下文相关的）。我想识别那些“正则表达式等效”的模式。在解决了以下问题后，我提出了这个问题：

我需要解析特定的文本格式，我首先尝试了正则表达式，我发现 regexp 足以解析它。然后我想为我收到的这种格式的消息制作一个 XML 表示，所以我用 XML 元素映射了正则表达式组。然后，我根据正则表达式的结构手动创建了一个 XSD 模式。最后，我有一个可以替换我的正则表达式的模式，从某种意义上说，原始的正则表达式可以从模式中构造出来。我还设法做相反的事情：从正则表达式自动创建模式。因此，我可以将消息转换为 XML 并同时对其进行验证。我的问题是：

1. 每个正则表达式都可以用 XSD 模式表示吗？（我的意思是，给定一个能够生成 XSD 模式的正则表达式）

2. 给定一个任意 XSD 模式，有没有办法确定是否存在一个表示给定模式的正则表达式？

   编辑：可能第一个问题的答案是肯定的，因为我用我的正则表达式做的，不依赖于特定的正则表达式（这不是每个正则表达式的证明）。

我正在阅读一本关于自动机理论的书，书中给出了一个示例，即具有相同数量的 0 和 1 的语言与 1*0* 相交会导致 1n0n，其中 n > 0

所以我的问题是，我怎样才能找到一些与 1*0* 相交时也会产生 1n0n 的常规语言。有没有办法考虑这个？

更新：感谢您的回答！我想我想要找到的是一些常规语言，所以像 1n0n 这样的语言是行不通的；）有可能吗？有任何想法吗？

首先，我不知道这是否是我所要求的正确翻译。

在我的一门课程中，我们只是盯着学习正则表达式、形式语言等。

在这种情况下，假设我从 1R 开始，然后我可以继续使用 1R 或 0R。

如果我从 1R 开始，那么只有 1....那么句子（在这种情况下是二进制数）是完整的，对吗？因为我不能在之后“附加”一些东西，所以说 1R 然后我选择 1 然后我再次选择 1R ？

在此先感谢，如果不正确，请重新标记/移动帖子。

添加：

如何生成 1100110？

这不是家庭作业，它是来自 powerpoint 的示例/问题。我不明白这是怎么做到的。

我正在研究一些测试准备材料并坚持这个问题。

显示 L = {we {a,b}*: w = wR 且每个 a 都紧跟 ab} 的上下文无关文法。

wR 是相反的 w。所以，在英语中，每个“a”后面跟着一个“b”的回文，使用任意数量的a和b。

到目前为止，我得到了这个反向部分，但我不知道如何合并每个 a 后跟 ab 部分，同时确保回文属性仍然有效。

任何帮助是极大的赞赏！

这是一个家庭作业问题：

我知道 L 是非常规的，并且我知道 Kleene Star 是一个封闭的操作，所以我的假设是 L_4 是非常规的。

然而，我的教授提供了一个上面的例子L = {0^p | p is prime}，他说这是规则的，通过证明这L*等于L(000* + e)说每个都是彼此的子集（在这种情况下，e 表示空词）。

所以他的方法涉及形成一个正则表达式0^p，但是当我基本上已经有了一个正则表达式时，我该怎么做呢？

假设 E = {a, b}。令 L0 = {(b^(n))(a^(2n)) : n >= 0}。令 L = ((不操作)L0)

L 是正则的、上下文无关的但不是正则的，还是不是上下文无关的？证明你的答案。

我正在寻找 L 是什么，以及如何以与问题中描述 L0 的方式类似的方式来描述它，以及答案。

解释对我来说很重要，如果您愿意贡献，请具体说明。我希望了解此材料以进行测试。

非常感谢！

我有一个清单：

我需要将所有 1,2,3... 替换为 '1', '2', '3'...并将 name1, name2, name3 替换为 'name1', 'name', 'name'3。我知道如何通过'\n'和'\s'来做到这一点。

但我认为存在更好的方法。有人知道这种方式吗？

这样的事情存在吗？如果是这样，你能举个例子吗？谢谢。

我很好奇哪些（如果有的话）现实世界的编程语言具有规则的语法（即所有语法正确的程序集都是规则的）。

另请参阅此问题：哪些编程语言是上下文无关的？.