How to generate languages using only two pairs of parentheses. (English) Zbl 0755.68091

Geffert, Viliam

J. Inf. Process. Cybern. 27, No. 5-6, 303-315 (1991).

It is shown that every phrase-structure grammar is equivalent to a grammar which has two erasing productions \(AB\to\varepsilon\), \(CD\to\varepsilon\), and all other productions are context-free. using this it is then proved that context-free productions and a single extra production \(ABC\to\varepsilon\) are sufficient. Both normal forms contain five nonterminals and their time and space complexities are the same as in the original grammar. The normal forms ar constructed directly from the original grammar.

Reviewer: P.Turakainen (Oulu)

MSC:

68Q42	Grammars and rewriting systems
68Q45	Formal languages and automata

Keywords:

normal forms