Context-sensitive grammar

related topics
{math, number, function}
{language, word, form}
{company, market, business}

A context-sensitive grammar (CSG) is a formal grammar in which the left-hand sides and right-hand sides of any production rules may be surrounded by a context of terminal and nonterminal symbols. Context-sensitive grammars are more general than context-free grammars but still orderly enough to be parsed by a linear bounded automaton.

The concept of context-sensitive grammar was introduced by Noam Chomsky in the 1950s as a way to describe the syntax of natural language where it is indeed often the case that a word may or may not be appropriate in a certain place depending upon the context. A formal language that can be described by a context-sensitive grammar is called a context-sensitive language.

Contents

Formal definition

A formal grammar G = (N, Σ, P, S) ( this is the same as G = (V, T, P, S) , just that the Non - Terminal V(ariable) is replaced by N and T(erminal) is replaced by Σ ) is context-sensitive if all rules in P are of the form

where AN (i.e., A is a single nonterminal), α,β ∈ (N U Σ)* (i.e., α and β are strings of nonterminals and terminals) and γ ∈ (N U Σ)+ (i.e., γ is a nonempty string of nonterminals and terminals).

Some definitions also add that for any production rule of the form u → v of a context-sensitive grammar, it shall be true that |u|≤|v|. Here |u| and |v| denote the length of the strings respectively.

In addition, a rule of the form

where λ represents the empty string is permitted. The addition of the empty string allows the statement that the context sensitive languages are a proper superset of the context free languages, rather than having to make the weaker statement that all context free grammars with no →λ productions are also context sensitive grammars.

The name context-sensitive is explained by the α and β that form the context of A and determine whether A can be replaced with γ or not. This is different from a context-free grammar where the context of a nonterminal is not taken into consideration. (Indeed, every production of a context free grammar is of the form V → w where V is a single nonterminal symbol, and w is a string of terminals and/or nonterminals (w can be empty)).

If the possibility of adding the empty string to a language is added to the strings recognized by the noncontracting grammars (which can never include the empty string) then the languages in these two definitions are identical.

Examples

This grammar generates the canonical non-context-free language  \{ a^n b^n c^n : n \ge 1 \} :

Full article ▸

related documents
Atlas Autocode
Double negative elimination
Weierstrass–Casorati theorem
Borel-Cantelli lemma
Hash collision
Subalgebra
Nowhere dense set
Magma computer algebra system
Category (mathematics)
Calculus with polynomials
Stirling number
Prefix code
Dyadic rational
Malleability (cryptography)
Algebraic number
T1 space
Cayley's theorem
C*-algebra
Steiner system
Byte-order mark
Sexagesimal
Algebraic extension
Residue (complex analysis)
Real line
Regular space
Extractor
Alternative algebra
Partial fractions in integration
Subtraction
GNU Octave