将上下文无关的语法转换为常规语法 [英] Converting a context free grammar into a regular grammar

问题描述

E->EAE |(E)|-E |ID

E -> EAE | (E) | -E | id

A->+ |-|* |/

A -> + | - | * | /

终端集为{id，-，+，*，/}，起始符号为E.

The terminal set is {id, -,+,*,/} and the starting symbol is E.

我想将此语法转换为常规语法.我尝试取消该语法的左递归，然后得到:

I want to convert this grammar to a regular grammar. I tried canceling the left recursion of this grammar and I got:

E->(E)X |-EX |idX

E -> (E)X | -EX | idX

A->+ |-|* |/

A -> + | - | * | /

X->AEX |ε

X -> AEX | ε

是它还是我需要做的其他事情?

Is this it or is there something else I need to do?

推荐答案

您注定要失败，因为您的语言不是常规语言.没有正确的常规语法.为了说明这种情况，我们可以使用Myhill-Nerode定理，该定理说常规语言的最小DFA具有与关于该语言的不可区分性关系上的等价类一样多的状态.如果我们可以显示出与您的语法语言可区分的无限多个字符串(我们将在下面进行说明)，那么这意味着您的语言的最小DFA将具有无限多个状态.DFA只能具有有限的多个状态，因此有效地意味着您知道您的语言不正常.

You are doomed to failure because your language is not a regular language. There cannot be a correct regular grammar for it. To show this is the case, we can use the Myhill-Nerode theorem which says that a minimal DFA for a regular language has as many states as there are equivalence classes over the indistinguishability relation with respect to the language. If we can show there are infinitely many strings distinguishable with respect to the language of your grammar - which we will do below - then that would imply a minimal DFA for your language would have infinitely many states. DFAs can only have finitely many states, so that effectively means you know your language isn't regular.

要显示有无限多个可区分的字符串，只需找到一个无限序列的字符串w1，w2，...，wn，...，就语言而言，每个字符串都可以与其他字符串区分开你的语法.我经常采用的一种方法是争论最短的字符串是什么，它将把我们序列中的每个字符串变成该语言中的字符串.如果您可以证明每个wi的最短字符串都与其他wi不同，那么您就可以了-因为如果其中的最短字符串长度不同，则两个集合就不可能相同.

To show there are infinitely many distinguishable strings, it suffices to find an infinite sequence of strings w1, w2, ..., wn, ... such that each one is distinguishable from all the others, with respect to the language of your grammar. One way I often approach this is to argue about what the shortest string is that will take each of the strings in our sequence to a string in the language. If you can show that each of the wi has a different shortest string than any of the others, you are done - since two sets cannot be the same if the shortest strings in them have different lengths.

要找到合适的序列，我们可以查看您的语法，并寻找似乎不规则的规则.E->EAE和E->(E)两者都似乎有问题.我的直觉是因为E->(E)更简单(涉及更少的非终结符)，使用起来会更容易.让我们定义单词w1，w2，...，wn，...的序列，利用该生成来获得可区分的字符串.如果该生产被反复使用，则E->.使用id时，您将获得(^ n id)^ n形式的字符串，其中括号是匹配的.这很重要-常规语言无法做到这一点.我们使用Myhill-Nerode对此进行显示，如下所示:

To find a suitable sequence, we can look at your grammar and look for rules that seem non-regular. E -> EAE and E -> (E) both seem problematic. My gut feeling is that because E -> (E) is simpler (it involves fewer nonterminal symbols) it will be easier to work with. Let's define a sequence of words w1, w2, ..., wn, ... that exploits this production to get strings that are distinguishable. If this production is used over and over again, and then E -> Id is used, you get strings of the form (^n id )^n, where the parentheses are matched. This is important - regular languages can't do this. We show this using Myhill-Nerode as follows:

假设语言是正常的.然后由Myhill-Nerode得出，最小DFA中的状态数是相对于语言在不可区分关系上的等价类数.考虑字符串的无限序列(，(((，...，(^ n，...可以附加到每个字符串中以获得该语言的字符串的最短字符串为Id)，Id))，..长度为3、4，...，n + 2，...的Id)^ n，...，这意味着每个字符串都可以彼此区分，因此存在无限多个等效类.这是一个矛盾，所以假设语言是常规的是错误的.

Assume the language is regular. Then by Myhill-Nerode, the number of states in a minimal DFA is the number of equivalence classes over the indistinguishability relation with respect to the language. Consider the infinite sequence of strings (, ((, ..., (^n, ... The shortest strings that can be appended to each of these to get a string in the language are Id), Id)), ..., Id)^n, ..., of lengths 3, 4, ..., n+2, ... This means that each of the strings is distinguishable from every other one, so there are infinitely many equivalence classes. This is a contradiction, so the assumption the language was regular was wrong.

这篇关于将上下文无关的语法转换为常规语法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！