Coincidental Extention of Scattered Context Languages

coincidental extention; scattered context languages

Coincidental extention of scattered context languages is introduced and discussed.

For a symbol, #, and a string, x = a_1 a_2 \ldots a_{n-1} a_n, any string of the form #^i a_1 #^i a_2 #^i \ldots #^i a_n-1 #^i a_n #^i, where i \geq 0, is a coincidental #-extension of x. A language, K, is a coincidental #-extension of L if every string o K represents a coi ncidental extension of a string in L and the deletion of all #s in K results in L. This paper proves that for every recursively enumerable language, E, there exists a propagating scattered context language that represents a coincidental extension of E.