zbMATH — the first resource for mathematics

Grammars with context dependency restricted to synchronization. (English) Zbl 0611.68050
Mathematical foundations of computer science, Proc. 12th Symp., Bratislava/Czech. 1986, Lect. Notes Comput. Sci. 233, 370-378 (1986).
[For the entire collection see Zbl 0596.00021.]
We found that each recursively enumerable language can be generated by a grammar with all of the rules being context-free, and a ”little more” - two extra rules AB\(\to \epsilon\), CD\(\to \epsilon\) (or a single extra rule ABC\(\to \epsilon)\). This corresponds to the fact that the information about context can be transferred and encoded by a string over a two-letter alphabet. Consequently, the research was concentrated on the ”gap” between recursively enumerable and context-free languages - a grammar with only one non-context-free rule AB\(\to \epsilon\), which corresponds to a transfer of context information restricted to one-letter alphabet (i.e. synchronization signals). A similar gap exists between context-sensitive and context-free languages, corresponding to monotonic grammars.

68Q45 Formal languages and automata