1. Reduction of context-free grammars
- Author
-
Kenichi Taniguchi and Tadao Kasami
- Subjects
ID/LP grammar ,Discrete mathematics ,Tree-adjoining grammar ,Terminal and nonterminal symbols ,Affix grammar ,Attribute grammar ,Noncontracting grammar ,General Engineering ,Context-sensitive grammar ,Mildly context-sensitive grammar formalism ,Algorithm ,Engineering(all) ,Mathematics - Abstract
This paper is concerned with the following problem: Given a context-free grammar G , find a context-free grammar with the fewest nonterminal symbols or with the fewest rules that is equivalent to G . A reduction procedure is presented for finding such a reduced context-free grammar that is structurally equivalent to a given G . On the other hand, it is proved that there is no finite procedure for finding such a reduced context-free grammar that is weakly equivalent to a given G .
- Published
- 1970
- Full Text
- View/download PDF