Uniform Generation of Languages by Scattered Context Grammars

Article type: Research Article

Authors: Meduna, Alexander

Abstract: The present paper discusses the uniform generation of languages by scattered context grammars. More specifically, it demonstrates that every recursively enumerable language can be generated by a scattered context grammar, G, so that every sentential form in a generation of a sentence has the form y_1…y_m u, where $u$ is a terminal word and each y_i is a permutation of either of two equally long words, z_1∈{A, B, C}* and z_2∈{A, B, D}*, where A, B, C, and D are G's nonterminals. Then, it presents an analogical result so that u precedes y_1…y_m.

Keywords: uniform rewriting, permutations, scattered context grammars

Journal: Fundamenta Informaticae, vol. 45, no. 3, pp. 231-235, 2001