问题标签 [formal-languages]

我想知道学习形式语言、自动机、算法和数据结构的最佳网站是什么。最好有许多已解决的问题...在此先感谢

我在一本关于可计算性的书中读到了这一点：

(Kleene's Theorem) 一种语言是规则的当且仅当它可以通过应用联合、连接、重复有限次数这三个操作从有限语言中获得。

我正在与“有限的语言”作斗争。

考虑这种语言：L = a*

它不是有限的。它{0, a, aa, aaa, ...}显然是一个无限集（0=空字符串）。

所以它是一种无限的语言，对吧？也就是说，“无限集”意味着“无限语言”，对吧？

显然，a*是一种常规语言。它是一种无限的语言。因此，根据 Kleene 定理，它不可能是常规语言。矛盾。

我很困惑。我想我不知道“有限语言”是什么意思。

我想知道是否存在用于基于形式语法生成输出的库（最好在 .NET 中）。

我说的是这个： https ://en.wikipedia.org/wiki/Chomsky_hierarchy#Formal_grammars

所以你给它的语法如下：

（非终结符号、终结符号、产生式规则、开始符号）

所以：

然后该库将生成该语法的示例随机输出，例如：

在创建或找到这样的库之后，我要做的是改变它产生输出的方式，使其更偏向于产生某些示例而不是其他示例，所以在前面的示例中，我可以使它更偏向用加法而不是乘法来产生更多的表达式。

因此，基本上为生产规则分配权重，以使其中一些在有多个有效规则时更有可能被应用。

所以我的主要问题是，是否有一个库可以执行第一步，即根据我的示例这样的形式语法生成随机输出？

更新

再次思考这个问题，我还有几点笔记：

• 这里的问题之一是知道何时停止应用生产规则。要么确保语法确实在某个点停止，要么在算法/代码中设计一种方法，使其不太可能继续扩展表达式。

• 我现在意识到这可能太理论化了，可能有更实用的方法。我的意思是，必须有一些工具基本上可以做同样的事情，但可能只是使用不同的语法或方法，这些语法或方法对某些问题更具体，或者可能更灵活。

我正在寻找描述以下语言的上下文相关语法：

我遇到了一个问题，即不允许使用诸如 X -> ε 之类的规则，因此我不能放置任何非终结符来指示单词的“中间”。这个问题有什么诀窍吗？
如果你碰巧知道答案，请帮忙。

我在 EBNF 中有这个语法，用于具有算术和逻辑表达式、变量分配和打印的子语言。

不幸的是，我无法弄清楚这两个规则是什么：
unExpr ::= + unExpr
unExpr ::= - unExpr
实际上是做什么的，或者为什么我需要它们，因为我似乎能够在不应用的情况下推导出语言的每个短语他们。任何想法？
多谢 ：-）

目标：找到一种正式定义语法的方法，该语法以任意顺序识别集合中的元素 0 或 1 次。随后，我想解析它并生成一个 AST。

例如：假设我的语言中的有效字符串集是{A, B, C}. 我想定义一个语法来识别任意数量的这些元素的所有有效排列。

语法上有效的字符串包括：

• （空字符串）
• A,
• B A， 和
• C A B

语法上无效的字符串包括：

• A A， 和
• B A C B

需要明确的是，在 CFG 中明确定义所有可能的排列对于我的目的是不可接受的，因为无法维护更大的集合。

据我了解，这种语言无法满足上下文无关语言的引理，因此该解决方案将不是上下文无关的或常规的。

更新

我所追求的被称为“置换语言”，Benedek Nagy作为上下文无关语言的扩展做了一些理论工作。

关于解析器生成器，我只发现了关于使用置换阶段（链接）实现解析器的讨论。解析器显然对生成的 CFG 的大小有一个指数下限，而且我还没有找到任何支持它的解析器生成器。

这个问题的一种解决方案是用 ANTLR 编写的。它使用语义谓词来“围绕”问题进行编码。

考虑这个简单的语法：

S -> 一个 | b

该文法可能生成的字符串集是：

{a, b}

因此，语法会生成一组字符串。

语法解析器接受输入字符串并确定该字符串是否可以由语法生成。

因此，解析器是语法的识别器。

至少，这是解析器的一种用途。

但通常解析器用于其他事情。例如，语法解析器可以获取输入字符串并创建一个包含输入数据并符合语法的树结构。

在这种情况下，解析器不是识别器，而是数据结构构建器。

我得出结论，有不同类型的解析器。

我在逻辑思考吗？确实有不同类型的解析器吗？

是否有人创建了解析器创建的不同类型事物的列表？

请让我知道上述陈述中的任何松散或歧义。我正在努力学习在关于这些概念的陈述中准确无误。例如，您是否同意“语法生成一组字符串”？那是精确的吗？正确的？

BNF（或EBNF）语法的第一个（最顶层）规则是否必须代表入口点？例如，从维基百科 BNF 页面，下面的美国邮政地址语法<postal-address>作为第一推导规则，也是入口点：

我是否可以自由地将<postal-address>规则放在第二个位置，因此以以下替代形式提供语法：

我刚开始学习形式语言和自动机理论，最近学习了正则表达式，所以我不知道任何复杂的符号，所以请坚持使用基本符号。

问题是：为以下语言编写一个正则表达式，{0, 1}它是一组所有奇数长度的字符串，其中正好包含两个0s。

我已经完成了第一部分（奇怪的部分），它应该是：

(0+1)[(0+1)(0+1)]*（与（或）+相同，|我相信，我们将其学习为+）

但是，当我想到正好有两个0s 时，它真的搞砸了。我只能看到我只能使用*with ，1因为 # of 0s 仅限于2. 但如果我这样做(11)*了，我就无法得到0s 在1s 中的排列。（例如不能得到10101）(11)*。

我知道的：

1. 只有1s 可以使用*
2. 在正则表达式中，只会0使用两个 s
3. 制作奇数长度的方法是将奇数长度添加到偶数长度（偶数长度需要在其中设置空字符串）
4. 奇数长度不应该使用*，因为 2 奇数 = 偶数，所以只有偶数长度可以使用*。

对于可能的提示或答案，请仅使用0, 1, +/ |, *, (, )。其他一些表达我将无法理解。

我是 python 新手，并试图在语法中生成所有可能的句子。这是语法：

这是我的尝试，我正在使用队列类来有条不紊地实现它，

我进入了无限循环，而且我也面临着一些浅深复制的问题，如果我更改一份 sf 副本，队列中的所有内容也会发生变化。任何帮助表示赞赏，任何方向，提示都会很棒

这是预期的输出：