证明正则语言和自动机
Prove regular language and automata
这是一种语法，我想检查一下这种语言是否正规。
L → ε | aLcLc | LL
例如这个语法的结果是：
acc, accacc ..., aacccc, acaccc, accacc, aaacccccc, ...
我知道那不是正规语言，但如何证明呢？构建自动机是证明它的正确方法吗？结果自动机是什么。我没有看到使用它来构建自动机的模式。
感谢您的帮助！
首先，让我快速证明，您不能仅根据语法不规则来推断语法语言是不规则的。要看到这一点，请考虑不受限制的语法：
S -> SSaSS | aS | e
SaS -> aSa
aaS -> SSa
这显然不是正则文法，但你应该能够验证它生成了 a 的所有字符串的无限正则语言。
也就是说，我们应该如何进行？我们需要弄清楚你的语法生成什么语言，然后争论特定语言不能是规则的。我们注意到引入终结符的唯一规则总是引入两倍于 a 的 c。此外，不难看出语言必须是无限的。我们可以使用 Myhill-Nerode 定理来证明这些观察意味着语言一定是不规则的。
考虑此语法语言中假设字符串的前缀 a^n。可以附加到此前缀末尾的最短字符串是 c^(2n)。没有更短的字符串可以工作，并且该字符串始终有效。现在想象一下，我们正在为文法语言寻找一个正确的确定性有限自动机。然后，无论处理前缀 a^n 的状态如何，我们都需要从那里到自动机中接受状态的最短路径长度为 2n。但是 DFA 必须有有限多个状态，并且 n 是任意自然数。我们的 DFA 不能对所有可能的 n 起作用（它需要有任意多个状态）。这是一个矛盾，所以对于文法的语言不可能有正确的 DFA。由于所有正则语言都有DFA，这意味着这种文法的语言不可能是正则的。
这是一种语法，我想检查一下这种语言是否正规。
L → ε | aLcLc | LL
例如这个语法的结果是：
acc, accacc ..., aacccc, acaccc, accacc, aaacccccc, ...
我知道那不是正规语言，但如何证明呢？构建自动机是证明它的正确方法吗？结果自动机是什么。我没有看到使用它来构建自动机的模式。
感谢您的帮助！
首先，让我快速证明，您不能仅根据语法不规则来推断语法语言是不规则的。要看到这一点，请考虑不受限制的语法：
S -> SSaSS | aS | e
SaS -> aSa
aaS -> SSa
这显然不是正则文法，但你应该能够验证它生成了 a 的所有字符串的无限正则语言。
也就是说，我们应该如何进行？我们需要弄清楚你的语法生成什么语言，然后争论特定语言不能是规则的。我们注意到引入终结符的唯一规则总是引入两倍于 a 的 c。此外，不难看出语言必须是无限的。我们可以使用 Myhill-Nerode 定理来证明这些观察意味着语言一定是不规则的。
考虑此语法语言中假设字符串的前缀 a^n。可以附加到此前缀末尾的最短字符串是 c^(2n)。没有更短的字符串可以工作，并且该字符串始终有效。现在想象一下，我们正在为文法语言寻找一个正确的确定性有限自动机。然后，无论处理前缀 a^n 的状态如何，我们都需要从那里到自动机中接受状态的最短路径长度为 2n。但是 DFA 必须有有限多个状态，并且 n 是任意自然数。我们的 DFA 不能对所有可能的 n 起作用（它需要有任意多个状态）。这是一个矛盾，所以对于文法的语言不可能有正确的 DFA。由于所有正则语言都有DFA，这意味着这种文法的语言不可能是正则的。