时间戳

首页 > 解决方案 > 证明正则语言和自动机

regular-language - 证明正则语言和自动机

问题描述

这是一种语法，我想检查这种语言是否正常。 

 L → ε | aLcLc | LL

例如这个语法的结果是：
acc, accacc ..., aacccc, acaccc, accacc, aaacccccc, ...

我知道这不是常规语言，但如何证明呢？构建自动机是证明它的正确方法吗？产生的自动机是什么。我没有看到使用它来构建自动机的模式。

感谢您的任何帮助！

标签： regular-languageformal-languages

解决方案

首先，让我快速证明你不能仅仅根据语法的不规则性来推断语法的语言是不规则的。要看到这一点，请考虑不受限制的语法：

S -> SSaSS | aS | e
SaS -> aSa
aaS -> SSa

这显然不是常规语法，但您应该能够验证它生成了所有 a 字符串的无限正则语言。

也就是说，我们应该如何进行？我们需要弄清楚你的语法生成了什么语言，然后争论特定的语言不可能是正则的。我们注意到引入终结符号的唯一规则总是引入两倍于它的 a。此外，不难看出语言必须是无限的。我们可以使用 Myhill-Nerode 定理来证明这些观察意味着语言必须是不规则的。

考虑该语法语言中假设字符串的前缀 a^n。可以附加到该前缀末尾以提供由该语法生成​​的字符串的最短字符串是 c^(2n)。没有更短的字符串会起作用，并且该字符串总是有效的。现在想象一下，我们正在为语法语言寻找一个正确的确定性有限自动机。然后，无论处理前缀 a^n 的状态使我们处于何种状态，我们都需要从那里到自动机中的接受状态的最短路径长度为 2n。但是 DFA 必须有有限多个状态，并且 n 是任意自然数。我们的 DFA 不能适用于所有可能的 n（它需要有任意多个状态）。这是一个矛盾，因此对于语法的语言不可能有正确的 DFA。由于所有常规语言都有 DFA，

推荐阅读