将上下文无关文法转换为常规文法
Converting a context free grammar into a regular grammar
E -> EAE | (E) | -E | id
A -> + | - | * | /
The terminal set is {id, -,+,*,/} and the starting symbol is E.
我想将此语法转换为常规语法。我试着取消这个语法的左递归，我得到：
E -> (E)X | -EX | idX
A -> + | - | * | /
X -> AEX | ε
是这样还是我还需要做其他事情？
你注定要失败，因为你的语言不是正规语言。它不可能有正确的正则语法。为了证明是这种情况，我们可以使用 Myhill-Nerode 定理，该定理表明常规语言的最小 DFA 具有与关于该语言的不可区分性关系的等价 类 一样多的状态。如果我们可以证明有无限多的字符串可以根据您的语法语言区分 - 我们将在下面进行 - 那么这意味着您的语言的最小 DFA 将具有无限多的状态。 DFA 只能有有限多个状态，因此这实际上意味着您知道您的语言是不规则的。
为了证明有无限多个可区分的字符串，找到一个无限的字符串序列 w1, w2, ..., wn, ...你的语法语言。我经常处理这个问题的一种方法是争论最短的字符串是什么，它将把我们序列中的每个字符串都变成语言中的一个字符串。如果您可以证明每个 wi 的最短字符串与其他任何一个都不同，那么您就完成了 - 因为如果两个集合中的最短字符串具有不同的长度，则这两个集合不可能相同。
要找到合适的顺序，我们可以查看您的语法并寻找看似不规则的规则。 E -> EAE 和 E -> (E) 似乎都有问题。我的直觉是，因为 E -> (E) 更简单（它涉及更少的非终结符号），所以更容易使用。让我们定义一个单词序列 w1, w2, ..., wn, ... 来利用这个产生式来获得可区分的字符串。如果反复使用此产生式，然后使用 E -> Id，您将得到 (^n id )^n 形式的字符串，其中括号匹配。这很重要——常规语言无法做到这一点。我们使用 Myhill-Nerode 显示如下：
假设语言是正则的。然后根据 Myhill-Nerode，最小 DFA 中的状态数是关于语言的不可区分性关系的等价数 类。考虑字符串的无限序列 (, ((, ..., (^n, ... 可以附加到每个字符串以获得语言中的字符串的最短字符串是 Id), Id)), .. ., Id)^n, ..., of lengths 3, 4, ..., n+2, ... 这意味着每个字符串都可以与其他字符串区分开来，因此有无限多个等价关系 类。这是一个矛盾，所以语言是正则的假设是错误的。
E -> EAE | (E) | -E | id
A -> + | - | * | /
The terminal set is {id, -,+,*,/} and the starting symbol is E.
我想将此语法转换为常规语法。我试着取消这个语法的左递归，我得到：
E -> (E)X | -EX | idX
A -> + | - | * | /
X -> AEX | ε
是这样还是我还需要做其他事情？
你注定要失败，因为你的语言不是正规语言。它不可能有正确的正则语法。为了证明是这种情况，我们可以使用 Myhill-Nerode 定理，该定理表明常规语言的最小 DFA 具有与关于该语言的不可区分性关系的等价 类 一样多的状态。如果我们可以证明有无限多的字符串可以根据您的语法语言区分 - 我们将在下面进行 - 那么这意味着您的语言的最小 DFA 将具有无限多的状态。 DFA 只能有有限多个状态，因此这实际上意味着您知道您的语言是不规则的。
为了证明有无限多个可区分的字符串，找到一个无限的字符串序列 w1, w2, ..., wn, ...你的语法语言。我经常处理这个问题的一种方法是争论最短的字符串是什么，它将把我们序列中的每个字符串都变成语言中的一个字符串。如果您可以证明每个 wi 的最短字符串与其他任何一个都不同，那么您就完成了 - 因为如果两个集合中的最短字符串具有不同的长度，则这两个集合不可能相同。
要找到合适的顺序，我们可以查看您的语法并寻找看似不规则的规则。 E -> EAE 和 E -> (E) 似乎都有问题。我的直觉是，因为 E -> (E) 更简单（它涉及更少的非终结符号），所以更容易使用。让我们定义一个单词序列 w1, w2, ..., wn, ... 来利用这个产生式来获得可区分的字符串。如果反复使用此产生式，然后使用 E -> Id，您将得到 (^n id )^n 形式的字符串，其中括号匹配。这很重要——常规语言无法做到这一点。我们使用 Myhill-Nerode 显示如下：
假设语言是正则的。然后根据 Myhill-Nerode，最小 DFA 中的状态数是关于语言的不可区分性关系的等价数 类。考虑字符串的无限序列 (, ((, ..., (^n, ... 可以附加到每个字符串以获得语言中的字符串的最短字符串是 Id), Id)), .. ., Id)^n, ..., of lengths 3, 4, ..., n+2, ... 这意味着每个字符串都可以与其他字符串区分开来，因此有无限多个等价关系 类。这是一个矛盾，所以语言是正则的假设是错误的。