nLab
mildly context-sensitive grammar

Contents

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:

  • multiple agreement L1={a nb nc n|a,b,cV,n},L1 = \{ a^n b^n c^n | a, b, c \in V, n \in \mathbb{N} \},
  • crossed dependency L2={a nb mc nd m|a,b,c,dV,m,n}L2 = \{ a^n b^m c^n d^m | a, b, c, d \in V, m, n \in \mathbb{N} \},
  • duplication L3={ww|wV }L3 = \{w w | w \in V^\star\}.

References

  • Shieber, Stuart M. Evidence against the context-freeness of natural language. Philosophy, Language, and Artificial Intelligence. Springer, Dordrecht, 1985.
  • Weir, David Jeremy. Characterizing mildly context-sensitive grammar formalisms, 1988.
  • Daniel Genkin, Nissim Francez, and Michael Kaminski. Mildly Context-Sensitive Languages via Buffer Augmented Pregroup Grammars, In Essays in Memory of Amir Pnueli, 2010.

Last revised on November 29, 2020 at 03:49:09. See the history of this page for a list of all contributions to it.