کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
435844 | 689944 | 2015 | 10 صفحه PDF | دانلود رایگان |
A deterministic L system generates an infinite word α if each word in its derivation sequence is a prefix of the next, yielding α as a limit. We generalize this notion to arbitrary L systems via the concept of prefix languages. A prefix language is a language L such that for all x,y∈Lx,y∈L, x is a prefix of y or y is a prefix of x. Every infinite prefix language determines a single infinite word. Where C is a class of L systems (e.g. 0L, DT0L), we denote by ω(C)ω(C) the class of infinite words determined by the prefix languages in C . This allows us to speak of infinite 0L words, infinite DT0L words, etc. We categorize the infinite words determined by a variety of L systems, showing that the whole hierarchy collapses to just three distinct classes of infinite words: ω(PD0L)ω(PD0L), ω(D0L)ω(D0L), and ω(CD0L)ω(CD0L). Our results are obtained with the help of a pumping lemma which we prove for T0L systems.
Journal: Theoretical Computer Science - Volume 595, 30 August 2015, Pages 1–10