我有一些关于正则表达式的问题。从我看到你只能使用*作为字母数，但如果我想写L = {a ^ n b ^ n | n> = 0}我将如何在正则表达式中显示字母数相等。
一般来说，如何在正则表达式中显示字母数之间的任何关系？
你在形式语言理论中找到了一个非常重要的想法 - 纯粹的/理论上的正则表达式与语言不匹配a ^ n b ^ n！这是一个重要的结果。 Myhill-Nerode定理是理解为什么会出现这种情况的一种很好的方法，但基本上，它归结为：如果你能证明没有有限的自动机可以接受这种语言，那么它就不是常规的，也没有正则表达式。
特别是对于您的语言，假设它是常规的并且有正则表达式。然后我们知道有一个接受语言的确定性有限自动机。我们可以进一步推断存在具有尽可能少的状态的确定性有限自动机 - 最小DFA。让此DFA中的状态数为p。现在，考虑我们语言中的字符串a ^ p b ^ p。由于状态数为p且字符串长度大于p-1，因此在处理此长度为2p的字符串时，DFA必须在某个时刻循环。设x是遍历此循环时处理的^ p b ^ p的子字符串。然后，由于我们的DFA接受^ p b ^ p，它还必须接受通过遍历循环任意次数获得的任何字符串，或者完全不遍历它。也就是说，我们可以去掉子串x，或者将它改为x ^ 2或x ^ k，并且该字符串也应该是我们的语言。是否有适合我们的x选择？事实证明，没有 - 无论我们选择的^ pb ^ p的哪个子串，更改出现次数都会给我们一个不在我们语言中的字符串（要么只更改一个字符串的数量，要么只更改b的数量） ，或中间的a和b的顺序）。因此，我们的DFA不存在，因此没有正则表达式。对于常规语言而言，这基本上是一个冗长的证明，这是另一种工具。
能够描述语言的能力最小（规范）计算系统是无上下文语言的类。无上下文语法可用于描述如何生成这些语言。您的语言的CFG是这样的：
S -> aSb
S -> epsilon
使用它的方法是从S（一个非终端开始符号）开始，然后使用产生（映射规则）来导出中间表达式，直到你留下一串只有终端符号（我们的终端符号是a和b） 。我们可以生成类似S - > aSb - > aaSbb - > aaaSbbb - > aaabbb的aaabbb。
现在，如果您询问使用“正则表达式”库的应用编程，这些通常会提供更多功能，允许捕获非常规语言。他们可能已经制作了那些不同寻常的怪物图灵等效，请检查GitHub是否只为“正则表达式”构建了Quake。