Construction of Pure Grammars

Abstract

A construction is described assigning a pure grammar G_{mrn} to any language and to any integers 0≤m≤r≤n. This construction has the following property: If the sequence (G_{mrn})_{n≥r} has a limit G_{mr} for any r≥m and if the sequence (G_{mr})_{r≥m} has a limit, then the given language is generated by a pure grammar. By a limit of a sequence (a_{k})_{k≥k_{0}} we understand a member a_{k_{1}} of the sequence such that k_{1}≥k_{0} and a_{k}=a_{k_{1}} for any k≥k_{1}.