无重叠生成文法的一义可解析性及图林等价性

为了实现有效的文法解析，定义了一种生成规则受限的短语结构文法，称为无重叠生成文法。证明了该类文法的任何语言句子都可以被无回朔无失败地解析。尽管该类文法的生成规则受到很大的限制．但这种文法的生成能力仍然和图灵机等同。

Uniquely parsable of overlap-free grammar and its turing universality

To implementation of efficient parsing of grammars,a new class of phrase structure grammars called overlap-free grammar(OFG) with heavily restricted rewriting rules is defined.It is shown that any sentences in any OFG language can be parsed successfully in a very sample way without backtracking.It is also shown that OFG is not only of non-backtracking uniquely parsability but also of universal generative ability,i.e.Turing equivalence or universality,in spite of the restrictions to its rewriting rules.