问题标签 [formal-languages]

常规语言在操作下关闭：

init(L) = 字符串 w 的集合，使得对于某些 x，wx 在 L 中。

编辑： x 可以是任何字符串、字符或空字符串我如何证明这一点？

有人可以解释堆栈翻译器的工作原理吗？我认为它主要用于词法分析（我可能非常错误）。欢迎任何其他材料或链接！谢谢 ！

如何为语言x^ay^bz^2(a+b)其中 a>=0, b>=0 构建上下文无关语法。感谢您的帮助...

Sudkamp 的语言和机器的问题 19.5要求读者验证语法

很强大LL(2)。变量的FIRST和FOLLOW集合S使用算法 19.5.1（第 583 页，第 3 版）计算：

很明显，S规则的长度为 2 的前瞻集不会对 的长度为 2 的前瞻集进行分区S，因为规则S -> λ导致长度为 2 的前瞻集包括FOLLOW(2)(S)：

现在有可能我在计算 、 或 的FIRST集合FOLLOW时LA(2)出错了G。但是，我相当有信心我已经正确执行了算法。特别是，我可以恢复他们的定义：

现在的问题是：为什么语法强LL(2)。如果S规则的长度为 2 的前瞻集不分割长度为 2 的前瞻集S，则语法不应该是强的LL(2)。但我无法得出本书所期望的结论。我不明白什么？

定义生成语言的 CFG（上下文无关语言）：

L={a^nb^mc^n | n,m>=0}

谁能告诉我如何解决这个问题？

我的理解是 L 由以下元素组成：{ aabbbcc }（我假设 n=2 和 m=3）

提前感谢约阿希姆

我确实需要你的帮助。我有这些作品：

我应该应用乔姆斯基范式（CNF）。

为了应用上述规则，我应该：

1. 消除ε产生
2. 消除酉产生
3. 删除无用的符号

我马上就卡住了。原因是 A 是可以为空的符号（ε 是其主体的一部分）

当然，我不能删除 A 符号。

谁能帮我得到最终的解决方案？

下面的语言L是不可判定的吗？

L = {米| M是图灵机描述，存在长度为k的输入x ，使得M在最多k步后停止}

我认为是，但我无法证明。我试图考虑减少停机问题。

我正在尝试理解语言级别的概念（常规、上下文无关、上下文相关等）。

我可以很容易地查到这个，但我找到的所有解释都是一堆符号和谈论集合。我有两个问题：

1. 你能用语言描述什么是常规语言，以及这些语言有什么不同吗？

2. 人们从哪里学会理解这些东西？据我了解，它是形式数学？我在大学有几门课程使用它，几乎没有人理解它，因为导师只是假设我们知道它。我在哪里可以学习它，为什么人们“期望”在这么多来源中知道它？好像教育有差距。

这是一个例子：

属于该集合的任何语言都是字母表上的常规语言。

一种语言怎么能“超越”任何东西？

我正在考虑利用一些空闲时间来设计和实施形式语言和自动机理论课程的教学工具。我正在尝试确定 OOP 实现是否合适，如果合适，是否有人可以建议对我在下面概述的设计进行高级改进。

语言分析中揭示了许多潜在的类别。一些（如果我错过了任何基本内容，请告诉我）是：语法；非终结符；终端; 生产; 常规语法；上下文无关语法；上下文相关的语法；不受限制的语法；自动机；状态; 象征; 过渡; DFA；NFA；NFA-拉姆达；DPDA；掌上电脑；体重秤；图灵机。

问题1：每种语法在实现中是否应该有自己的类，或者一个总体语法类是否应该有方法来确定它是哪种语法（例如，“isRegular()”、“isContextFree()”等.) （更一般地说，在领域模型中只有一点点不同的类，并且仅在行为方面，应该通过实现中的继承来表示，还是将不同类型的行为简单地推送到父类中更好？）

问题 2：“Symbol”、“State”、“Nonterminal”等是否应该在实现中拥有自己的类，还是应该由它们的容器控制？ （更一般地说，是否应该在实现中为域模型中的非常简单的类赋予它们自己的类 - 例如为了可扩展性 - 还是应该将其推入容器类中？）

问题 3：Transition 在实现中是否应该是它自己的类，如果是，我是否需要对它进行子类化以支持每种自动机（因为除了在状态方面有所不同，它们在发生的情况方面也有所不同在过渡期间）？ （更一般地说，有两个抽象父类，其中一个的孩子和另一个的孩子之间存在双射......耦合是一种好习惯吗？）

我意识到，归根结底，很多这些决策只是设计决策，但我想知道你们对 OOP 设计中的最佳实践有何看法。此外，我不只是将“更普遍”的问题作为纯 OOP 设计问题提出的原因是，我希望从具有此类领域（语言和自动机）经验的人那里获得特殊的观点。

任何帮助是极大的赞赏。

1、我有一个可以识别“aa”和“epsilon”两个词的NFA。所以这个 NFA 识别的语言 L1 是一个集合 {aa, epsilon}。这种语言的长度是多少？是 |L1| = 1？或 |L1| = 2？

2，假设我有另一个可以识别一个单词“aa”的NFA。所以语言 L 将是一个集合 {aa} 在形式语言中，epsilon 属于每一种语言。因此实际上 L2 包含 epsilon，即一个集合 {aa, epsilon} 那么这种语言 L2 的长度是多少？1 还是 2？

谢谢