nLab
mildly context-sensitive grammar

Contents

Idea

Mildly context-sensitive grammar is a kind of formal grammar with an expressivity between that of context-free grammar and context-sensitive grammar. They have enough expressive power to capture natural languages, but not too much so that they are still parsable efficiently.

Definition

While there has been no consensus on the definition of “mild”, there is an equivalence [VW94] between several independent definitions, see Weir (1988). Borrowing the definition from Genkin et al. (2010), a grammar formalism is mildly context-sensitive if the languages it generates are semilinear, it is parsable in polynomial time, it contains all context-free languages as well as the following:

References