问题标签 [formal-languages]

有人可以解释和之间的确切区别Σ*，语言L*在哪里， L语言Σ的字母在L哪里？

谢谢

所以这不是关于抽水引理及其工作原理，而是关于先决条件。

在网络上你可以读到的任何地方，常规语言都必须通过抽引引理，但是没有人谈论有限语言，它实际上是常规语言的一部分。

所以我们可能都同意，以下语言是一种有限语言，也是一种常规语言，但它绝对没有通过抽水引理：

L = {'abc', 'defghi'}

请告诉我是否根本没有人写它，或者我们为什么错了——甚至没有。

由其描述给出的常规语言：

{0,1, a} 的所有字符串的集合，其中包含子字符串 '01a' 和偶数个 '1'。例如，“01a1”、“101a”、“101a101”。

如何构造一个指定语言的正则表达式？

我理解图灵机的逻辑。当给出图灵机时，我可以理解它是如何工作的以及它是如何停止的。但是当它被要求构建一个图灵机时，它就更加困难了。

有什么简单的方法可以找到以下问题的答案：

我想绘制这些图灵机的图表？有没有什么方法，比如填表然后画图等等？

我在网上搜索了很多关于这个主题的内容。只有答案（只有图表）。没有解释它是如何解决的。

提前致谢

我试图在 C 中为 XML 文件构建小型解析器。我知道，我可以找到一些完成的解决方案，但是，我只需要一些用于嵌入式项目的基本东西。我正在尝试创建用于描述没有属性的 XML 的语法，只有标签，但它似乎不起作用，我无法弄清楚原因。

这是语法：

这是实现此语法的 C 代码的一部分：

}

编辑：这是不满足此语法的 XML 文件示例：

它在输出端给出 END EXPECTED。

在形式语言的乔姆斯基分类中，我需要一些Non-Linear, Unambiguous and also Non-Deterministic上下文无关语言（N-CFL）的例子吗？

1. 线性语言：线性语法是可能的（⊆ CFG），例如
   L ₁ = {a ⁿ b ⁿ | n≥0}

2. 确定性上下文无关语言（D-CFG）：确定性下推自动机（D-PDA）是可能的，例如
   L ₂ = {a ⁿ b ⁿ c ^m | n ≥ 0, m ≥ 0 }
   L ₂是明确的。

非线性的 CF 文法是非线性的。
L _nl = {w: n _a (w) = n _b (w)} 也是非线性 CFG。

-- 3. Non-Deterministic Context Free Language(N-CFG) :only Non-Deterministic Push-Down-Automata(N-PDA)可能的例如
L ₃ = {ww ^R | w ∈ {a, b} ^* }
L ₃也是线性CFG。

--4。模棱两可的 CFL : only ambiguous CFG is possible
L ₄ = {a ⁿ b ⁿ c ^m |的 CFL n ≥ 0, m ≥ 0 } U {a ⁿ b ^m c ^m | n ≥ 0, m ≥ 0 }
L ₄既是非线性又是模糊 CFG 和每个模糊 CFL \subseteq N-CFL。

我的问题是：
是否所有非线性、非确定性 CFL 都是模棱两可的？如果不是，那么我需要一个非线性、非确定性 CFL 且明确的示例？

给定下面的维恩图：

也在这里问

我想知道构建电子邮件地址的正式定义。

我不只是想要答案，而是如何得到它，因为我想自己学习如何去做。

我需要一些帮助来解决抽水引理问题。

这是我到目前为止得到的：

我让 y = abbc^n，n 是来自抽水引理的长度。y 在 L 中是因为 a:s 的数量小于 b:s 的数量，并且 b:s 的数量小于 c:s 的数量。

我让 u = a，v = bb 和 w = c^n。|紫外线| < y，如抽水引理中所述。如果我“抽” (bb)^2 那么我得到

这是正确的吗 ？我在“正确的道路”上吗？

谢谢

我需要一些帮助来为上下文无关语法构建 LR(0) DFA。

这就是我所拥有的：

状态

然后我有一个标记a为：

状态

从这个状态，一个箭头标记a为：

状态：

这就是我的问题开始的地方。正如你所看到的，我从这个状态得到两个箭头B，因为我有：

我做错了什么？

我很难理解 LR(1) 中的前瞻原理 - 项目。如何计算前瞻集？

举个例子，我有以下语法：

然后第一个状态将如下所示：

我知道前瞻是什么，但我不知道如何计算它们。我已经用谷歌搜索了答案，但找不到以简单方式解释这一点的网页。

提前致谢