An extended Earley's algorithm for Petri net controlled grammars without λ rules and cyclic rules

摘要

In this paper we introduce an algorithm which solves the membership problem of Petri net controlled grammars without λ-rules and cyclic rules. We define a conditional tree which is a modified derivation tree of a context-free grammar with information about control by a Petri net. It is shown that a conditional tree is cancelled to a derivation tree without conditions if and only if there is a derivation under the control of the Petri net from the start symbol to a word which is the yielding of the conditional tree. Then the Earley's algorithm is extended to make a conditional tree in addition to parse a word. Thus the word is generated by a given Petri net controlled grammar if and only if the resulting conditional tree is cancelled to a tree of no condition. The time complexity of the algorithm is nondeterministic polynomial of the length of an input word. Therefore the class of languages generated by Petri net controlled grammars without λ-rules and cyclic rules is included in the class of context-sensitive languages.