Construction of Pure Grammars

Article type: Research Article

Authors: Novotný, Miroslav

Affiliations: Faculty of Computer Science, Masaryk University, Botanická 68a, 602 00 Brno, Czech Republic

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}.

Keywords: generalized pure grammar, pure grammar, relation of domination, reducing operator

Journal: Fundamenta Informaticae, vol. 52, no. 4, pp. 345-360, 2002