𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A generator of context-sensitive languages

✍ Scribed by Ben Wegbreit

Publisher
Elsevier Science
Year
1969
Tongue
English
Weight
252 KB
Volume
3
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

✦ Synopsis

The existence of a context-sensitive grammar, G~, which acts as a "generator" of all context-sensitive languages is established. Specifically, G~ has the property that for each context-sensitive language, L, there exists a regular set, RL, and an e-limited gsm, gL, such that L = gz(L(G,,) ~ .RL). It follows that the family of context-sensitive languages is a principal AFL. An analogous result is proved for deterministic contextsensitive languages.

πŸ“œ SIMILAR VOLUMES

An hierarchy between context-free and co
An hierarchy between context-free and context-sensitive languages
✍ Takumi Kasai πŸ“‚ Article πŸ“… 1970 πŸ› Elsevier Science 🌐 English βš– 718 KB

Infinite subfamilies ~l, ~ .... , -oq'~o, .W,~ of the family consisting of contextsensitive languages, are introduced such that .2'~ ~z~ ..-C ~| ~o,where 9 LP a is the family of e-free context-free languages, Ld,o is the family of context-sensitive languages, and each L/', is an Abstract Family of L

Growth-sensitivity of context-free langu
Growth-sensitivity of context-free languages
✍ Tullio Ceccherini-Silberstein; Wolfgang Woess πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 265 KB

A language L over a ΓΏnite alphabet is called growth-sensitive if forbidding any set of subwords F yields a sub-language L F whose exponential growth rate is smaller than that of L. It is shown that every (essentially) ergodic non-linear context-free language of convergent type is growth-sensitive. "