Uniform rewriting based on permutations

Abstract

This paper explains how to transform grammars so that they generate their languages in a uniform way. Specifically, it transforms any phrase-structure grammar to an equivalent three-nonterminal phrase-structure grammar in which every sentential form consists of a terminal word followed by the concatenation of several permutations of a word over {0, 1}, where 0 and 1 are two of the three nonterminals. Then, it converts any phrase-structure grammar to an equivalent three-nonterminal phrase-structure grammar in which every sentential form consists of a terminal word preceded by the concatenation of several permutations of a binary word. In addition, it describes analogical transformations for EIL systems. In its conclusion, this paper discusses some open problems and applications.

Keywords:

• Uniform rewriting
• phrase-structure grammars
• L systems
• permutations

C.R. Categories:

• F4.2.1