Editing Context-sensitive grammar (section)

==Formal definition==

=== Formal grammar ===
Let us notate a [[formal grammar]] as <math>G = (N, \Sigma, P, S)</math>, with <math>N</math> a set of nonterminal symbols, <math>\Sigma</math> a set of terminal symbols, <math>P</math> a set of production rules, and <math>S \in N</math> the start symbol.

A string <math>u \in (N \cup \Sigma)^*</math> ''directly yields'', or ''directly derives to'', a string <math>v \in (N \cup \Sigma)^*</math>, denoted as <math>u \Rightarrow v</math>, if ''v'' can be obtained from ''u'' by an application of some production rule in ''P'', that is, if <math>u = \gamma L \delta</math> and <math>v = \gamma R \delta</math>, where <math>(L \to R) \in P</math> is a production rule, and <math>\gamma, \delta \in (N \cup \Sigma)^*</math> is the unaffected left and right part of the string, respectively.
More generally, ''u'' is said to ''yield'', or ''derive to'', ''v'', denoted as <math>u \Rightarrow^* v</math>, if ''v'' can be obtained from ''u'' by repeated application of production rules, that is, if <math>u = u_0 \Rightarrow ... \Rightarrow u_n = v</math> for some ''n'' ≥ 0 and some strings <math>u_1, ..., u_{n-1} \in (N \cup \Sigma)^*</math>. In other words, the relation <math>\Rightarrow^*</math> is the [[reflexive transitive closure]] of the relation <math>\Rightarrow</math>.

The '''language''' of the grammar ''G'' is the set of all terminal-symbol strings derivable from its start symbol, formally: <math>L(G) = \{ w \in \Sigma^* \mid S \Rightarrow^* w \}</math>.
Derivations that do not end in a string composed of terminal symbols only are possible, but do not contribute to ''L''(''G'').

=== Context-sensitive grammar ===
A formal grammar is '''context-sensitive''' if each rule in ''P'' is either of the form <math>S \to \varepsilon</math> where <math>\varepsilon</math> is the [[empty string]], or of the form
: α''A''β → αγβ
with ''A'' ∈ ''N'',<ref group="note">i.e., ''A'' a single [[nonterminal]]</ref> <math>\alpha, \beta\in (N \cup \Sigma \setminus\{S\})^*</math>,<ref group="note">i.e., α and β strings of nonterminals (except for the start symbol) and [[Terminal symbol|terminals]]</ref> and <math>\gamma\in (N \cup \Sigma \setminus\{S\})^+</math>.<ref group="note">i.e., γ is a nonempty string of nonterminals (except for the start symbol) and terminals</ref>

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.
By contrast, in a [[context-free grammar]], no context is present: the left hand side of every production rule is just a nonterminal.

The string γ is not allowed to be empty.  Without this restriction, the resulting grammars become equal in power to [[unrestricted grammar]]s.<ref name="Vide1999" />

=== (Weakly) equivalent definitions ===
A [[noncontracting grammar]] is a grammar in which for any production rule, of the form ''u'' → ''v'', the length of ''u'' is less than or equal to the length of ''v''.

Every context-sensitive grammar is noncontracting, while every noncontracting grammar can be converted into an equivalent context-sensitive grammar; the two classes are [[weak equivalence (formal languages)|weakly equivalent]].<ref>{{cite book |last1=Hopcroft |first1=John E. |url=https://archive.org/details/introductiontoau00hopc |title=Introduction to Automata Theory, Languages, and Computation |last2=Ullman |first2=Jeffrey D. |publisher=Addison-Wesley |year=1979 |isbn=9780201029888 |author-link1=John Hopcroft |author-link2=Jeffrey Ullman |url-access=registration}}; p.&nbsp;223–224; Exercise 9, p.&nbsp;230. In the 2003 edition, the chapter on CSGs has been omitted.</ref>

Some authors use the term ''context-sensitive grammar'' to refer to noncontracting grammars in general.

The '''left-context'''- and '''right-context'''-sensitive grammars are defined by restricting the rules to just the form α''A'' → αγ and to just ''A''β → γβ, respectively. The languages generated by these grammars are also the full class of context-sensitive languages.<ref name="Hazewinkel1989">{{cite book |last=Hazewinkel |first=Michiel |url=https://books.google.com/books?id=s9F71NJxwzoC&pg=PA297 |title=Encyclopaedia of Mathematics |publisher=Springer Science & Business Media |year=1989 |isbn=978-1-55608-003-6 |volume=4 |page=297 |author-link=Michiel Hazewinkel}} also at https://www.encyclopediaofmath.org/index.php/Grammar,_context-sensitive</ref> The equivalence was established by [[Penttonen normal form]].<ref name="ItoKobayashi2010">{{cite book |last1=Ito |first1=Masami |url=https://books.google.com/books?id=xuaR2bJq0rcC&pg=PA183 |title=Automata, Formal Languages and Algebraic Systems: Proceedings of AFLAS 2008, Kyoto, Japan, 20–22 September 2008 |last2=Kobayashi |first2=Yūji |last3=Shoji |first3=Kunitaka |publisher=World Scientific |year=2010 |isbn=978-981-4317-60-3 |page=183}} citing {{Cite journal |last1=Penttonen |first1=Martti |date=Aug 1974 |title=One-sided and two-sided context in formal grammars |journal=[[Information and Control]] |volume=25 |issue=4 |pages=371–392 |doi=10.1016/S0019-9958(74)91049-3 |doi-access=free}}</ref>