Editing Context-sensitive grammar (section)

=== (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>