
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

On the Generative Capacity of LexicalFunctional Grammars
Ryuichi NAKANISHI Hiroyuki SEKI Tadao KASAMI
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E75D
No.4
pp.509516 Publication Date: 1992/07/25 Online ISSN:
DOI: Print ISSN: 09168532 Type of Manuscript: PAPER Category: Automaton, Language and Theory of Computing Keyword: lexicalfunctional grammars, formal language, automata, generative capacity,
Full Text: PDF>>
Summary:
LexicalFunctional Grammars (LFG's) were introduced to define the syntax of natural languages. In LFG's, each node of a derivation tree has some attributes. An LFG G consists of a contextfree grammar (cfg) G_{0} called the underlying cfg of G and a description P_{fs} of constraints between the values of the attributes. P_{fs} can specify (1) constraints between the value of an attribute of a node and those of its children, and (2) constraints between the value of an attribute of a node called a controller and that of a node called its controllee. RLFG's were introduced as a subclass of LFG's. In RLFG's, only constraints between the value of an attribute of a node and those of its children can be specified. It is shown in this paper that the class of languages generated by RLFG's is equal to the class of recursively enumerable languages. Some restrictions on LFG's were proposed for the purpose of efficient parsing. Among them are (1) the condition called a valid derivation, and (2) the condition that the underlying cfg is cyclefree. For an RLFG G, if the production rules of the underlying cfg of G are of the form AaB or Aa for nonterminal symbols A, B and a terminal symbol a, then G is called an RRLFG. Every RRLFG satisfies the above restriction (1) and (2). It is also shown in this paper that the class of languages generated by RRLFG's contains an NPhard language, which means that parsing in deterministic polynomial time of LFG's is impossible in general (unless PNP) even if the above restrictions (1) and (2) are satisfied.

