On the Generative Capacity of Lexical-Functional Grammars

Ryuichi NAKANISHI  Hiroyuki SEKI  Tadao KASAMI  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E75-D   No.4   pp.509-516
Publication Date: 1992/07/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Automaton, Language and Theory of Computing
Keyword: 
lexical-functional grammars,  formal language,  automata,  generative capacity,  

Full Text: PDF>>
Buy this Article



Summary: 
Lexical-Functional 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 context-free grammar (cfg) G0 called the underlying cfg of G and a description Pfs of constraints between the values of the attributes. Pfs 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 cycle-free. 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 R-RLFG. Every R-RLFG satisfies the above restriction (1) and (2). It is also shown in this paper that the class of languages generated by R-RLFG's contains an NP-hard 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.