zbMATH — the first resource for mathematics

How to generate languages using only two pairs of parentheses. (English) Zbl 0755.68091
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.

MSC:
 68Q42 Grammars and rewriting systems 68Q45 Formal languages and automata
normal forms