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

##### MSC:
 68Q45 Formal languages and automata