nLab context-sensitive grammar

Contents

Contents

 Idea

Context-sensitive grammar is a kind of formal grammar with an expressive power between that of context-free grammar and unrestricted grammar, they are at the second level of Chomsky hierarchy.

Definition

A context-sensitive grammar is a tuple (V,X,R,s)(V, X, R, s) where VV and XX are disjoint finite sets of terminal and non-terminal symbols with sXs \in X, RR is a finite set of rules αxγαβγ\alpha x \gamma \to \alpha \beta \gamma for a non-terminal symbol xXx \in X, strings of symbols α,γ(V+X) \alpha, \gamma \in (V + X)^\star and a non-empty string β(V+X) +\beta \in (V + X)^+.

In order to make the context-free languages a proper subset of the context-sensitive languages, the rule s1s \to 1 is allowed for 11 the empty string.

Example

Any context-free language is also context-sensitive. The language L={a mb mc m|m1}L=\{a^m b^m c^m| m\geq 1\} is context-sensitive but a classical application of the pumping lemma? shows that LL is not context-free.

Properties

The parsing problem, i.e. given a grammar GG and a string αV \alpha \in V^\star decide whether αL(G)\alpha \in L(G) is PSPACE?-complete. Thus, it is suspected to be infeasible to solve efficiently. This motivated the definition of mildly context-sensitive grammar.

Last revised on October 16, 2021 at 09:51:08. See the history of this page for a list of all contributions to it.