Lecture 1 min.
Context-sensitive grammar (CS grammar, context grammar) is a special case of a formal grammar (type 1 in the Chomsky hierarchy) in which the left and right sides of all productions may be surrounded by terminal and nonterminal symbols.
The context-free grammar is also a special case of a formal grammar.
A language that can be generated by a CS grammar is called a context-sensitive language, or CS language.
A formal grammar G=(N, T, I, P) is context-sensitive if all rules in P have the form: αAβ → αωβ
where A ∈ N (that is, a single nonterminal symbol), ω ∈ (N ∪ T)+ (that is, a nonempty string consisting of terminal and/or nonterminal symbols), and α, β ∈ (N ∪ T)* (that is, any string consisting of terminal and/or nonterminal symbols).
The following grammar generates the context-sensitive language 
:
This is what the derivation of the string aaa bbb ccc looks like:
Comments