问题标签 [kleene-star]

我这样做是为了家庭作业。a我需要为 ( , ) 上的语言编写一个正则表达式，b其中包括语言中未包含的所有字符串(a*b)*

例如'aaaaaaabaaaaaaaaaaaaaaaabaaaaaaaaaaaaab' 会起作用。所以我正在为所有不包含在其中的字符串寻找一个正则表达式。

你能帮我至少找到正确的步骤吗？

我知道这a*b意味着a我们想要多少个，后面跟着一个b。然后就是我们想要的次数。

令 L = {一个ⁿ | n >= 0}，其中所有n >= 1。

因此 L 由所有长度的 a 序列组成，包括长度为 0 的序列。设 L2 是 L 的任何无限子集。我需要证明总是存在一个 DFA 来识别 (L2)*。

如果 L2 是有限子集，则非常明显，因为 L2 将是 DFA，因此通过克莱恩闭包，L2* 将被 DFA 识别。但是我无法为无限子集得到它，因为 L2 可能不会表示为 DFA，例如字符串的长度是素数。

I'm trying to create the context free grammar which generates all regular expressions over {a,b} with at least one Kleene star. What I've done so far is this:

I suppose this can generate all regular expressions, but what I can't get my head around is how to define it so that at least one Kleene star needs to be in that expression.

令 G = (V,E,r) 一个有根有向图，由一组顶点 V 和一组边 E 与指定的根节点 r 定义。该图可能包含循环。任务：给定 V 中的两个顶点 x 和 y，找出从 x 到 y 的所有路径。

由于允许循环，因此路径集显然可能是无限的。因此，我想以正则表达式（Kleene Algebra）的形式找到一组路径。以下是一些示例：示例图表。乘法表示序列，因此路径 abc 表示首先 a，然后是 b，然后是 c。一组路径 a(b+c+d) 表示首先是 a，然后是 b、c 或 d。kleene 星 a* 表示 a 重复零次或多次，a+ 表示 a 重复一次或多次。

现在我正在寻找一种通过算法构造这些表达式的方法。到目前为止我想出了什么：

• 构造新的表达式树 T。
• 在结束节点 y 处开始搜索。
• 找到所有前辈 p 到 y。
• 对于每个 p：
  • 将 p 作为子节点添加到 T 中的 y。
  • 回溯从 p 到根的树上的路径。如果沿途找到 y，则从 y 到 p 存在一个循环。因此，不仅 p 是 y 的前身，而且 (path)* 也是 p 的前身。因此，将 (path)* 作为子节点添加到 p。
  • 对于所有非循环的前辈，递归调用 y := p 作为新的结束节点。

最后：

• 反转树，使其以结束节点结束
• 将表达式树转换为表达式（直截了当）

不确定这是否可行，但是，我猜最坏情况的复杂性也会高于 2^n。有谁知道这个或类似问题的算法？

设n为任意终端。

考虑以下可能正确的 kleene 星在n上的表示：

（其中 ε 是空终端。）

维基百科说：

乔姆斯基范式中的每个语法都是上下文无关的，相反，每个上下文无关的语法都可以转换为乔姆斯基范式中的等效语法。

我看不出如何将上述语法转换为 CNF。

• 语法不是上下文无关的吗？
• 实际上有没有办法在 CNF 中表示它？

对于给定的上下文无关文法：

如何重写语法使其成为 LR(1)？
当前语法在解析输入“id : .id”时存在移位/减少冲突，其中“。” 是解析器的输入指针。
该文法产生满足正则表达式 (id:(id)*)+ 的语言

我正在寻找提供解决此问题的算法的参考资料：

问题：给定一个有限字母 Σ 和一个有限语言 L ⊆ Σ ^*，确定 L ^*是否是一个自由幺半群。

等效地，问题是确定给定一组有限的字符串，这些字符串的每个连接是否可以使用相同的字符串唯一地分解。例如，任何字符串大小相同的语言都会满足这个条件，语言 L = {a, ba} 也会满足这个条件，但是语言 L = {ab, ba, aba} 不满足条件，因为字符串ababa可以被分解为ab aba或aba ba。

我目前正在学习自动机理论课程，但遇到了以下问题。我想出了第一个问题的答案，但对第二个问题的陈述感到困惑。

(i) 给出语言 S* 的递归定义，其中 S = {aa,b}。

第 1 步：Lamba、aa、b 在 S 中。

步骤 2：如果 x 在 S 中，那么 bx 和 xb 也是。

我想确认我的确认我的回答。

以下是我完全困惑的问题，无法想出答案。

(ii) 给出语言 T* 的递归定义，其中 T = {w1, w2, w3, w4} 其中这些 w 是一些特定的词。

我正在阅读一篇关于编程语言工程和编译器的论文（6.035 Fall 2005 MIT course）。下面的页面应该解释了 Kleene Star 操作符的工作原理，但我无法理解它的含义。

完整的 .pdf 可以在这里找到。

我一直试图证明两个正则表达式是等价的。我知道如果两个正则表达式定义相同的语言，它们是等价的。但是如果不使用 DFA，我就无法证明这一点。

例如，我有问题要证明以下是等价的。

我知道这两种语言都定义了至少有一个“a”和一个“b”的语言。

下面的情况也是如此。

任何帮助将不胜感激。

谢谢