Contents

Linguistics

# 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^n b^n c^n | a, b, c \in V, n \in \mathbb{N} \},$
• crossed dependency $L2 = \{ a^n b^m c^n d^m | a, b, c, d \in V, m, n \in \mathbb{N} \}$,
• duplication $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.