text:
Context-sensitive grammar

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, in the sense that there are languages that can be described by a CSG but not by a context-free grammar. Context-sensitive grammars are less general (in the same sense) than unrestricted grammars. Thus, CSGs are positioned between context-free and unrestricted grammars in the Chomsky hierarchy.

A formal language that can be described by a context-sensitive grammar, or, equivalently, by a noncontracting grammar or a linear bounded automaton, is called a context-sensitive language. Some textbooks actually define CSGs as non-contracting,  although this is not how Noam Chomsky defined them in 1959. This choice of definition makes no difference in terms of the languages generated (i.e. the two definitions are weakly equivalent), but it does make a difference in terms of what grammars are structurally considered context-sensitive; the latter issue was analyzed by Chomsky in 1963.

Chomsky introduced context-sensitive grammars as a way to describe the syntax of natural language where it is often the case that a word may or may not be appropriate in a certain place depending on the context. Walter Savitch has criticized the terminology "context-sensitive" as misleading and proposed "non-erasing" as better explaining the distinction between a CSG and an unrestricted grammar.

Although it is well known that certain features of languages (e.g. cross-serial dependency) are not context-free, it is an open question how much of CSGs' expressive power is needed to capture the context sensitivity found in natural languages. Subsequent research in this area has focused on the more computationally tractable mildly context-sensitive languages. The syntaxes of some visual programming languages can be described by context-sensitive graph grammars.

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

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

The language of the grammar G is the set of all terminal-symbol strings derivable from its start symbol, formally: $$L(G) = \{ w \in \Sigma^* \mid S \Rightarrow^* w \}$$. 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 $$S \to \varepsilon$$ where $$\varepsilon$$ is the empty string, or of the form
 * αAβ → αγβ

with A ∈ N, $$\alpha, \beta\in (N \cup \Sigma \setminus\{S\})^*$$, and $$\gamma\in (N \cup \Sigma \setminus\{S\})^+$$.

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 grammars.

(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 weakly equivalent.

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. The equivalence was established by Penttonen normal form.

anbncn
The following context-sensitive grammar, with start symbol S, generates the canonical non-context-free language { anbncn | n ≥ 1 } :

Rules 1 and 2 allow for blowing-up S to anBC(BC)n−1; rules 3 to 6 allow for successively exchanging each CB to BC (four rules are needed for that since a rule CB → BC wouldn't fit into the scheme αAβ → αγβ); rules 7–10 allow replacing a non-terminal B or C with its corresponding terminal b or c, respectively, provided it is in the right place. A generation chain for aaabbbccc is:
 * S
 * →2 aSBC
 * →2 aaSBCBC
 * →1 aaaBCBCBC
 * →3 aaaBCZCBC
 * →4 aaaBWZCBC
 * →5 aaaBWCCBC
 * →6 aaaBBCCBC
 * →3 aaaBBCCZC
 * →4 aaaBBCWZC
 * →5 aaaBBCWCC
 * →6 aaaBBCBCC
 * →3 aaaBBCZCC
 * →4 aaaBBWZCC
 * →5 aaaBBWCCC
 * →6 aaaBBBCCC
 * →7 aaabBBCCC
 * →8 aaabbBCCC
 * →8 aaabbbCCC
 * →9 aaabbbcCC
 * →10 aaabbbccC
 * →10 aaabbbccc

anbncndn, etc.
More complicated grammars can be used to parse { anbncndn | n ≥ 1 }, and other languages with even more letters. Here we show a simpler approach using non-contracting grammars: Start with a kernel of regular productions generating the sentential forms $$(ABCD)^{n}abcd$$ and then include the non contracting productions $$p_{Da} : Da\rightarrow aD$$, $$p_{Db} : Db\rightarrow bD$$, $$p_{Dc} : Dc\rightarrow cD$$, $$p_{Dd} : Dd\rightarrow dd$$, $$p_{Ca} : Ca\rightarrow aC$$, $$p_{Cb} : Cb\rightarrow bC$$, $$p_{Cc} : Cc\rightarrow cc$$, $$p_{Ba} : Ba\rightarrow aB$$, $$p_{Bb} : Bb\rightarrow bb$$, $$p_{Aa} : Aa\rightarrow aa$$.

ambncmdn
A non contracting grammar (for which there is an equivalent CSG) for the language $$L_{Cross} = \{ a^mb^nc^{m}d^{n} \mid m \ge 1, n \ge 1 \}$$ is defined by
 * $$p_1 : R\rightarrow aRC | aC$$,
 * $$p_3 : T\rightarrow BTd | Bd$$,
 * $$p_5 : CB\rightarrow BC$$,
 * $$p_0 : S \rightarrow RT$$,
 * $$p_6 : aB\rightarrow ab$$,
 * $$p_7 : bB\rightarrow bb$$,
 * $$p_8 : Cd\rightarrow cd$$, and
 * $$p_9 : Cc\rightarrow cc$$.

With these definitions, a derivation for $$a^3b^2c^3d^2$$ is: $$S \Rightarrow_{p_0} RT \Rightarrow_{p^{2}_{1}p_{2}} a^3C^3T \Rightarrow_{p_{3}p_{4}   } a^3C^3B^2d^2 \Rightarrow_{p^{6}_{5}    } a^3B^2C^3d^2 \Rightarrow_{p_{6}p_{7}   } a^3b^2C^3d^2 \Rightarrow_{p_{8}p^{2}_{9}} a^3b^2c^3d^2 $$.

a2 i
A noncontracting grammar for the language { a2 i | i ≥ 1 } is constructed in Example 9.5 (p. 224) of (Hopcroft, Ullman, 1979):

\ [Ca]a\rightarrow aa[Ca] \\ \ [Ca][aB]\rightarrow aa[CaB] \\ \ [ACa]a\rightarrow [Aa]a[Ca] \\ \ [ACa][aB]\rightarrow [Aa]a[CaB] \\ \ [ACaB]\rightarrow [Aa][aCB] \\ \ [CaB]\rightarrow a[aCB] \end{cases}$$ \ a[Da]\rightarrow [Da]a \\ \ [aDB]\rightarrow [DaB] \\ \ [Aa][Da]\rightarrow [ADa]a \\ \ a[DaB]\rightarrow [Da][aB] \\ \ [Aa][DaB]\rightarrow [ADa][aB] \end{cases}$$ \ a[Ea]\rightarrow [Ea]a \\ \ [aE]\rightarrow [Ea] \\ \ [Aa][Ea]\rightarrow [AEa]a \end{cases}$$
 * 1) $$S\rightarrow [ACaB]$$
 * 2) $$\begin{cases}
 * 1) $$[aCB]\rightarrow [aDB]$$
 * 2) $$[aCB]\rightarrow [aE]$$
 * 3) $$\begin{cases}
 * 1) $$[ADa]\rightarrow [ACa]$$
 * 2) $$\begin{cases}
 * 1) $$[AEa]\rightarrow a$$

Kuroda normal form
Every context-sensitive grammar which does not generate the empty string can be transformed into a weakly equivalent one in Kuroda normal form. "Weakly equivalent" here means that the two grammars generate the same language. The normal form will not in general be context-sensitive, but will be a noncontracting grammar.

The Kuroda normal form is an actual normal form for non-contracting grammars.

Equivalence to linear bounded automaton
A formal language can be described by a context-sensitive grammar if and only if it is accepted by some linear bounded automaton (LBA). In some textbooks this result is attributed solely to Landweber and Kuroda. Others call it the Myhill–Landweber–Kuroda theorem. (Myhill introduced the concept of deterministic LBA in 1960. Peter S. Landweber published in 1963 that the language accepted by a deterministic LBA is context sensitive. Kuroda introduced the notion of non-deterministic LBA and the equivalence between LBA and CSGs in 1964. )

it is still an open question whether every context-sensitive language can be accepted by a deterministic LBA.

Closure properties
Context-sensitive languages are closed under complement. This 1988 result is known as the Immerman–Szelepcsényi theorem. Moreover, they are closed under union, intersection, concatenation, substitution, inverse homomorphism, and Kleene plus.

Every recursively enumerable language L can be written as h(L) for some context-sensitive language L and some string homomorphism h.

Computational problems
The decision problem that asks whether a certain string s belongs to the language of a given context-sensitive grammar G, is PSPACE-complete. Moreover, there are context-sensitive grammars whose languages are PSPACE-complete. In other words, there is a context-sensitive grammar G such that deciding whether a certain string s belongs to the language of G is PSPACE-complete (so G is fixed and only s is part of the input of the problem).

The emptiness problem for context-sensitive grammars (given a context-sensitive grammar G, is L(G)=∅ ?) is undecidable.

As model of natural languages
Savitch has proven the following theoretical result, on which he bases his criticism of CSGs as basis for natural language: for any recursively enumerable set R, there exists a context-sensitive language/grammar G which can be used as a sort of proxy to test membership in R in the following way: given a string s, s is in R if and only if there exists a positive integer n for which scn is in G, where c is an arbitrary symbol not part of R.

It has been shown that nearly all natural languages may in general be characterized by context-sensitive grammars, but the whole class of CSGs seems to be much bigger than natural languages. Worse yet, since the aforementioned decision problem for CSGs is PSPACE-complete, that makes them totally unworkable for practical use, as a polynomial-time algorithm for a PSPACE-complete problem would imply P=NP.

It was proven that some natural languages are not context-free, based on identifying so-called cross-serial dependencies and unbounded scrambling phenomena. However this does not necessarily imply that the class of CSGs is necessary to capture "context sensitivity" in the colloquial sense of these terms in natural languages. For example, linear context-free rewriting systems (LCFRSs) are strictly weaker than CSGs but can account for the phenomenon of cross-serial dependencies; one can write a LCFRS grammar for {anbncndn | n ≥ 1} for example.

Ongoing research on computational linguistics has focused on formulating other classes of languages that are "mildly context-sensitive" whose decision problems are feasible, such as tree-adjoining grammars, combinatory categorial grammars, coupled context-free languages, and linear context-free rewriting systems. The languages generated by these formalisms properly lie between the context-free and context-sensitive languages.

More recently, the class PTIME has been identified with range concatenation grammars, which are now considered to be the most expressive of the mild-context sensitive language classes.

title: Context-sensitive grammar


text:
Context-sensitive language

In formal language theory, a context-sensitive language is a language that can be defined by a context-sensitive grammar (and equivalently by a noncontracting grammar). Context-sensitive is known as type-1 in the Chomsky hierarchy of formal languages.

Computational properties
Computationally, a context-sensitive language is equivalent to a linear bounded nondeterministic Turing machine, also called a linear bounded automaton. That is a non-deterministic Turing machine with a tape of only $$kn$$ cells, where $$n$$ is the size of the input and $$k$$ is a constant associated with the machine. This means that every formal language that can be decided by such a machine is a context-sensitive language, and every context-sensitive language can be decided by such a machine.

This set of languages is also known as NLINSPACE or NSPACE(O(n)), because they can be accepted using linear space on a non-deterministic Turing machine. The class LINSPACE (or DSPACE(O(n))) is defined the same, except using a deterministic Turing machine. Clearly LINSPACE is a subset of NLINSPACE, but it is not known whether LINSPACE = NLINSPACE.

Examples
One of the simplest context-sensitive but not context-free languages is $$L = \{ a^nb^nc^n : n \ge 1 \}$$: the language of all strings consisting of $n$ occurrences of the symbol "a", then $n$ "b"s, then $n$ "c"s (abc, aabbcc, aaabbbccc, etc.). A superset of this language, called the Bach language, is defined as the set of all strings where "a", "b" and "c" (or any other set of three symbols) occurs equally often (aabccb, baabcaccb, etc.) and is also context-sensitive.

$L$ can be shown to be a context-sensitive language by constructing a linear bounded automaton which accepts $L$. The language can easily be shown to be neither regular nor context-free by applying the respective pumping lemmas for each of the language classes to $L$.

Similarly: $$L_\textit{Cross} = \{ a^mb^nc^{m}d^{n} : m \ge 1, n \ge 1 \}$$ is another context-sensitive language; the corresponding context-sensitive grammar can be easily projected starting with two context-free grammars generating sentential forms in the formats $$a^mC^m$$ and $$B^nd^n$$ and then supplementing them with a permutation production like $$CB\rightarrow BC$$, a new starting symbol and standard syntactic sugar.

$$L_{MUL3} = \{ a^mb^nc^{mn} : m \ge 1, n \ge 1 \}$$ is another context-sensitive language (the "3" in the name of this language is intended to mean a ternary alphabet); that is, the "product" operation defines a context-sensitive language (but the "sum" defines only a context-free language as the grammar $$S\rightarrow aSc|R$$ and $$R\rightarrow bRc|bc$$ shows). Because of the commutative property of the product, the most intuitive grammar for $$L_\textit{MUL3}$$ is ambiguous. This problem can be avoided considering a somehow more restrictive definition of the language, e.g. $$L_\textit{ORDMUL3} = \{ a^mb^nc^{mn} : 1 < m < n \}$$. This can be specialized to $$L_\textit{MUL1} = \{ a^{mn} : m > 1, n > 1 \}$$ and, from this, to $$L_{m^2} = \{ a^{m^2} : m > 1 \}$$, $$L_{m^3} = \{ a^{m^3} : m > 1 \}$$, etc.

$$L_{REP} = \{ w^{|w|} : w \in \Sigma^* \}$$ is a context-sensitive language. The corresponding context-sensitive grammar can be obtained as a generalization of the context-sensitive grammars for $$L_\textit{Square} = \{ w^2 : w \in \Sigma^* \}$$, $$L_\textit{Cube} = \{ w^3 : w \in \Sigma^* \}$$, etc.

$$L_\textit{EXP} = \{ a^{2^n} : n \ge 1 \}$$ is a context-sensitive language.

$$L_\textit{PRIMES2} = \{ w : |w| \mbox { is prime } \}$$ is a context-sensitive language (the "2" in the name of this language is intended to mean a binary alphabet). This was proved by Hartmanis using pumping lemmas for regular and context-free languages over a binary alphabet and, after that, sketching a linear bounded multitape automaton accepting $$L_{PRIMES2}$$.

$$L_\textit{PRIMES1} = \{ a^p : p \mbox { is prime } \}$$ is a context-sensitive language (the "1" in the name of this language is intended to mean a unary alphabet). This was credited by A. Salomaa to Matti Soittola by means of a linear bounded automaton over a unary alphabet (pages 213-214, exercise 6.8) and also to Marti Penttonen by means of a context-sensitive grammar also over a unary alphabet (See: Formal Languages by A. Salomaa, page 14, Example 2.5).

An example of recursive language that is not context-sensitive is any recursive language whose decision is an EXPSPACE-hard problem, say, the set of pairs of equivalent regular expressions with exponentiation.

Properties of context-sensitive languages

 * The union, intersection, concatenation of two context-sensitive languages is context-sensitive, also the Kleene plus of a context-sensitive language is context-sensitive.
 * The complement of a context-sensitive language is itself context-sensitive a result known as the Immerman–Szelepcsényi theorem.
 * Membership of a string in a language defined by an arbitrary context-sensitive grammar, or by an arbitrary deterministic context-sensitive grammar, is a PSPACE-complete problem.

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

title: Context-sensitive language


text:
Talk:Chomsky hierarchy

=Topics from 2001=

Added a table
I've added a table to Chomsky hierarchy, and moved some of the information from the bullets to the table. I thought it would be easier to see the relationships at a glance if they were in a table. Feel free to resurrect the old bullets (below) if you think that's more readable. -LC [28 August 2001]

The old description
I've reinserted the old description because I feel it is more understandable and gives more explanation for people who don't know the hierarchy already. -- JanHidders [28 August 2001]
 * well then I'd hate to see the old description because the current one is incomprehensible. --Ignignot 03:26, Dec 13, 2004 (UTC)

Definitions and Chomsky-n term
I've fixed the definitions (nonempty γ, Type-1 includes S->&epsilon). I also removed the redundant A->a, for simplicity, and for consistency with some theory books.

I'm curious about the names "Chomsky-n" and "(CHn)". I've always heard people talk of "Type-n" grammars and languages, but not "Chomsky-n" languages. None of my books have it either. A web search turns up lots of hits on "Type-0 grammar" but none on "Chomsky-0". The same is true for the papers archived at. Is this term in widespread use? Or did a textbook coin it for internal use? -LC [28 August 2001]

Listing 3 rule types
I agree with the repair of the Type-1 grammer definition but then you should add a remark at CH1 that the rule S -> ε is also allowed. That way it is indeed the most common form. (I just did some checking in the library.) But for regular grammars the most common form is where all three types of rules are allowed. An important exception is the book by Hopcroft and Ullman Introduction to Automata and Language Theory where they only allow A -> aB and A -> a with the remark that S -> ε is also allowed. Actually I like their approach the best: Two arguments: (1) the book is a classic, (2) it makes it immediately clear that every higher type grammar is more restrictive than the lower type grammars. The discussion about the alternative definitions and why they are equivalent can always be done in the articles on the specific type of grammer. Deal? :-)
 * 1) type-0 : no restrictions
 * 2) type-1 : αAβ -> αγβ (with γ <> ε) and maybe S -> ε
 * 3) type-2 : A -> γ (with γ <> ε) and maybe S -> ε
 * 4) type-3 : A -> a or A -> aB and maybe S -> ε

As far as the "Chomsky-n" names are concerned, I didn't introduce those and I also haven't seen them anywhere before. The hierarchy is usually presented as a hierarchy of grammars and not of languages, so I feel we should do the same. -- JanHidders [28 August 2001]

About definitions
I agree. These definitions make it clearer that each is a superset of the next. That's nice. I'll go ahead and change the table to use those definitions. The "maybe S->ε" part can go in a sentence after the table, since it also needs to explain that if you use that form, you can't have S on the right side for Type-1.

I changed it from a hierarchy of languages to a hierarchy of grammars, and got rid of the "Chomsky-n" and "CHn" names before, but it slipped back in when the bullets were re-expanded. I'll make that change again. -LC [1-Sept-2001]

The definition of regular languages that was in the table (namely, using A --> a and not A --> \epsilon) was technically wrong, since it will not allow the generation of any regular language that contains the empty word. I've changed this to allow the A --> \epsilon production rule. The discussion above about different ways to present regular languages might be interesting to push in the article, but for now, the diagram should not be incorrect. -dam

=Topics from 2003=

Example third production
Shouldn't the third production in the example grammar be changed as follows:

OLD:
 * BA -> AB

NEW:
 * AB -> AABB

I don't see where BA can ever be generated when starting with S. This change seems like it would make it so that the grammar could indeed produce { anbn | n ∈ Integers & n >= 0 } as described. Right now it looks like it can only produces { ε, ab } (never being able to use several of the productions). - [67.30.5.76, 25 October 2003] S -> ABS -> ABABS -> AABBS -> AABb -> AAbb -> Aabb -> aabb. However, it would be nicer to give an example of a language that is not context-free. --Zero 12:25, 25 Oct 2003 (UTC)
 * It is correct. BA can be generated using the first production twice. For example

Alternatively, the same language could be codified with a context-free grammar of only two productions and one nonterminal: S -> aSb; S -> ε.

Useful links for further work
 *
 *

I'm not an expert on formal grammars, so forgive me if I'm wrong, but with the example grammar given for anbn:

it seems you can reach a state where no more productions are possible yet you still have non-terminals in the string:

S ABS (S -> ABS) AB (S -> ε)

There's no production rule for AB, nor A alone or B alone. Is there an error?

Also I agree that the simple context-free grammar S -> aSb; S -> ε may be a better example. What do people think?

Chopchopwhitey 20:49, 22 Nov 2003 (UTC)

 * It is not an error to be able to reach a point where no productions apply. The definition of the language generated by the grammar is the set of strings of all terminals that can be produced.  It doesn't matter what other strings can be produced. --Zero 02:43, 23 Nov 2003 (UTC)

 * Ok, thanks for clearing that up for me. --Chopchopwhitey 08:28, 23 Nov 2003 (UTC)

=Topics from 2004=

Splitting subset grammars
The linked page pushdown automaton makes a distinction between the deterministic and non-deterministic varieties of PAs and the languages that can be generated by each. Would it be correct to say this causes a splitting of Type-2 grammars into:

Type-2a - recognizable by NPA

Type-2b - recognizable by DPA ?

A sentence about this would be helpful.

marsh @{1} mysteray \.{1} com

 * Not exactly. It would be more correct to say that you have Type-2 grammars (recognizable by NPAs) and Type-2.5 grammars (recognizable by DPAs) where the first describes a proper superset of the second, and the second describes a proper superset of the languages described by Type-3 grammars. -- Jan Hidders 22:52, 16 Feb 2004 (UTC)

The names "type n grammar" and "type n language" for n in 0..3 are used by Chomsky in his original article (On Certain Formal Properties of Grammars, Information and Control 1959), so I think it is best to use them here as well. The purpose of the article is to prove that the four types of languages are separated by proper inclusions, so I think it is best to keep discussion of other types of grammars and languages introduced later (deterministic context-free languages, LR(k) and LL(k) languages, simple context-free languages, bracketed languages) out of this entry. -- rp 9 mar 2004

 * Then where should other formal languages be discussed, for example, indexed grammars/languages (Type 1.5) (Aho, 1968), mildly context-sensitive grammars/languages (1.75) (Joshi et al, 1975), and deterministic PDAs (2.5), among others. They certainly deserve treatment somewhere in a hierarchy of formal languages, even if Chomsky didn't discuss them in his 1959 and 1963 papers.  --jonsafari 23:03, 20 May 2006 (UTC)

In his original article, Chomsky does not consider empty productions or languages with empty strings, but the fact that empty string generation can always be "pushed out" to a single production is so fundamental that perhaps it must be discussed here rather than in a separate node. -- rp 9 mar 2004

=Topics from 2005=

Finitely many productions.
I've added to the given definition of a grammar the stipulation that the set of productions must be finite. This restriction needs to be placed either on all grammars, or on each of the classes used to define the Chomsky hierarchy for the article to be correct. I've chosen the former since this is consistent with the definition in formal grammar. Of course one can argue that there's nothing in principle wrong with the idea of an "infinite grammar" and that this idea is useful in certain contexts, but I think that debate is better had in the context of that article! Best wishes, Cambyses 10:21, 21 July 2005 (UTC)

Ironic name
Does anyone else find the title of this page ironic? Chomsky hierarchy--I know it isn't a hierarchy over people, but still, it is kinda funny. - [63.205.15.166, 11 September 2005]
 * What is funny about a categorization scheme for grammars of different languages? Perhaps you are referring to Chomsky's advocation of anarchosyndicalism which is inherently opposite a hierarchy.  —optikos 02:32, 19 September 2006 (UTC)
 * I also found it funny. "What did you say?  The Chomsky hierarchy?  I thought he was supposed to be an anarchist..."  82.32.31.166 (talk) 07:07, 31 March 2012 (UTC)

=Topics from 2006=

Schützenberger
The article says nothing about Marcel Schützenberger. I added a line, but it seems there should be more info (some references?) on this. Mhym 19:55, 14 March 2006 (UTC)

 * I don't understand why he is included in the title. I've read quite a lot of linguistics and computer science and never have I once heard the hierarchy called the Chomsky–Schützenberger hierarchy. In fact, I've never even heard of Schützenberger at all. If you look at the reference it's from a manual for "Nooj Computational Devices". Not exactly a strong reference for computer science theory or linguistics. In every book I can think of Hopcraft and Ullman, Lewis and Papadimitrous, any of Pinker's books on languages, even books by people who hate Chomsky like Terrance Deacon (Symbolic Species) or Georg Lakoff (Women Fire and Dangerous Things) it is always just called the Chomsky language hierarchy. Unless someone can provide a better reference I'm going to remove Schützenberger's name from the Intro. MadScientistX11 (talk) 22:17, 16 February 2023 (UTC)
 * It does seem to be a very unusual naming (at least, searching Chomsky Schutzenburger only turned up Chomsky–Schützenberger representation theorem, for the first dozen-ish pages), but I did find what seems like a reliable reference. So it seems to be the case that someone, on the planet, calls it the Chomsky–Schützenberger hierarchy. It could still be a case of WP:CITOGENESIS but there is that 1963 paper so Schützenberger did have some involvement. IDK, maybe in the future there will be a detailed Chomsky bio so we can properly apportion credit. But the name "Chomsky hierarchy" seems set in stone at this point and I think the early 2006-ish references to Chomsky–Schützenberger hierarchy should all be changed back to Chomsky hierarchy. Mathnerd314159 (talk) 02:59, 13 May 2023 (UTC)
 * I changed this a long time ago and removed Schützenberger's name. I saw someone changed it back a while ago and I've been to busy to get into an edit war so I just left it. I'm glad someone else took the time to change it back and since there is now a clear consensus, let's keep it that way. I've read quite a bit of linguistics both for cognitive and computer science and in the many things I've read about the Chomsky hierarchy, I've never seen Schützenberger's name. --MadScientistX11 (talk) 13:45, 19 December 2023 (UTC)
 * Someone just add it back. I'm deleting it and leaving them a note to take to the Talk page before adding it back. MadScientistX11 (talk) 01:38, 5 July 2024 (UTC)

Categorization addition
Given how important the hierarchy is to computer science, especially in the development of programming languages shouldn't there be a categorization link to either Category: Computer Science of Category: Programming Languages?

Why does this matter?
I came across this somewhat accidentally, and it left me wondering: why does this matter? Not that I doubt that it does, of course. It's just that the article doesn't say much about why this division of grammars is interesting or important. If someone knows, it would be great if they could add it. William Pietri 06:06, 10 July 2006 (UTC)

 * There are so many ways it matters. To start in the 1950's people thought FSMs could parse natural language. Chomsky proved this was impossible. For another, when you design a compiler you need to study this to understand why you can use one technique to implement the Lexical Analyzer (the thing that detects individual letters and punctuation) and a more complex technique to build the parser (because the lexical analyzer can be parsed by an FSA but the parser for a programming language requires a Push Down Automata. I agree it would be good to add this stuff. I just don't have time to do it justice right now because it requires some serious work. I hope someone else can do it, if not I'll make a note to come back when I have more time. MadScientistX11 (talk) 22:21, 16 February 2023 (UTC)

Page name change
Back in March, an editor moved this page from Chomsky hierarchy to Chomsky–Schützenberger hierarchy.

The name "Chomsky–Schützenberger hierarchy" has very little currency, as Google search will immediately verify. Hits for "Chomsky hierarchy" outnumber "Chomsky-Schützenberger hierarchy" by 68,000 to 15.

Regardless of the justness or aptness for the name "Chomsky hierarchy", that is what the subject of the article is called, and that is what the article should be named.

There are many similar cases; for example the Zorn's lemma article is under "Zorn's lemma", not "Kuratowski's lemma" or "Kuratowski-Zorn lemma" or "Zorn-Kuratowski lemma", because, in English, the lemma in question is universally known as "Zorn's lemma", despite the fact that Zorn enunciated a different (albiet related) maximal principle, and that Zorn's work was indisputably anticipated by Kuratowski.

Accordingly, I am moving this article back to Chomsky hierarchy. If Schützenberger made significant contributions to it, the article should say so in detail. But it should not be titled "Chomsky-Schützenberger hierarchy" when hardly anyone calls it that. -- Dominus 13:49, 13 September 2006 (UTC)

 * I also agree. See my comment up above. I also think we should remove "Chomsky-Schützenberger hierarchy" from the intro. I've never heard it called that and I've read a lot of computer science theory and linguistics (I site some sources in my previous comment up above). And the one reference for "Chomsky-Schützenberger hierarchy" is a computer manual for "Nooj Computational Devices". Not a book on CS theory or linguistics. Unless someone provides a better reference I'm removing Schützenberger from the intro. MadScientistX11 (talk) 22:24, 16 February 2023 (UTC)

Addendum: All of the cited references are for Chomsky, none for Schützenberger. The "external link" refers to "Chomsky hierarchy", no mention of Schützenberger.

-- Dominus 13:53, 13 September 2006 (UTC)

 * I wholeheartedly agree with this analysis and this corrective action. —optikos 02:13, 19 September 2006 (UTC)

Containment hierarchy
Mention in made in the Chomsky hierarchy entry of a "containment hierarchy". What is it? How does a containment hierarchy differ from other types of formal hierarchies? What are the other types of formal hierarchies?
 * If you need an explanation of a term that is linked to another Wikipedia article, then click on that link and read about the concept at the other article. This matter is fully addressed in containment hierarchy. —optikos 02:32, 19 September 2006 (UTC)
 * It just means that each level below is included in the level above. I actually think "subsumption hierarchy" is a better term although they mean more or less the same thing, people usually use subsumption hierarchy when talking about sets and subsets which is what the Chomsky hierarchy is and containment hierarchies when talking about things like a Bill of Materials in manufacturing.

Not too technical
Unless someone can explicitly itemize how this article is too technical or does not properly link to prerequisite background material needed to understand this widely-taught computer science concept, then the { { technical } } demerit needs to be removed, because this article is now very accessible and provides numerous links to prerequisite background material. This article is babified as much as it can possibly be and still discuss anything remotely related to the Chomsky hierarchy of grammars and the computability/expressivity implications. (And this article does a very bad job in the computability/expressivity department just to keep it babified for the masses.) Quite honestly we computer scientists do not take kindly to complaints such as "ooOOOOooo, it makes my head hurt" regarding our subject matter. I have heard ever since diagramming sentences in 6th grade how much people hate structured grammar in every one of its forms of presentation. It is time for the topic to get some respect! —optikos 02:32, 19 September 2006 (UTC)
 * I agree; see below: Removing technical-tag. -Wikid77 21:44, 14 October 2007 (UTC)

 * Amen. I hate "drive by tagging". I know tags have their place but far too many editors just slap a tag on something without giving a good rational. This is a very complex topic and you can't do it justice without getting technical. MadScientistX11 (talk) 22:27, 16 February 2023 (UTC)

=Topics from 2007=

Retrofitting topic subheaders
14-Oct-2007: I have inserted 12 subheaders above, retrofitting subheader titles to reflect the subject of each discussion, and adding "-[ ]" when missing. To emphasize the span of prior years, I have noted "Topics from 2001" or "Topics from 2003" etc. I moved 3 paragraphs according to the year the topic was started. There's not enough to archive the talk, and of course, some people added sub-comments in later years, as dated. -Wikid77 21:02, 14 October 2007 (UTC)

Removing technical-tag
24-Oct-2007: I am removing the "" tag from this talk page: it is a waste of time to try rewriting grammar production rules for a "general audience". Encyclopedias, historically, have been separated from science encyclopedias, but Wikipedia does not bias knowledge to prevent linking "physics" to an article about "hummingbirds" and their wings. Also, that tag is an access barrier which prompts computer scientists to feel they cannot use technical terms in WP articles. The technical-tag probably applies to well over 20,000 articles, and the appropriate solution is not to rewrite articles, but to "also-see" link back to general intro articles, not spend hours rewriting computability theory or quantum mechanics for "the masses". I'm afraid the technical-tag is just another vanity-tag that does more for those who use it, then actually helping readers or editors improve articles. The technical-tag, along with many other vanity-tags, should really be eliminated totally from Wikipedia, except as a historical reminder of failed concepts. Anyway, I am commenting out the "" tag here (and please also remove it from other talk-pages). -Wikid77 21:24, 14 October 2007 (UTC)

Set Inclusions
The set inclusion context-free\subseteq context-sensitive shown in the figure doesn't follow from the definition, for there is nothing to prevent productions of the type S-->aS, S-->\epsilon which according to the given definitions is a context-free grammar but not a context-sensitive grammar! —Preceding unsigned comment added by 113.199.200.196 (talk) 15:55, 20 September 2010 (UTC)

Arrow
What does the arrow pointing to the right symbolize? 169.139.19.207 (talk) 00:08, 7 March 2012 (UTC)
 * It symbolizes a production rule. It means that in a word from the formal language, the symbols on the left can be substituted by the symbols on the right, to create a new "expanded" word. This is explained in the linked article Formal_grammar. Diego (talk) 10:22, 7 March 2012 (UTC)

=Topics from 2012=

Some thoughts on regular vs. type-3 grammars
I've written down some thoughts on the distinction between regular and type-3 grammars at http://dp.grhack.net/#type_3_vs_regular_grammars. I think there are some problems with the examples presented in this wiki page. Can someone verify?

Nonterminal
The article says: "a finite set of nonterminal symbols (that do not appear in the left-hand side of any production rule)". I think this is not correct. — Preceding unsigned comment added by LCamel (talk • contribs) 04:13, 29 April 2012 (UTC)

So, which one is English?
Does this have any relation to, you know, real languages? Sagittarian Milky Way (talk) 17:54, 21 June 2012 (UTC)

 * I'm not a computational linguist, so you might want to take this with a grain of salt, but as far as I'm aware this is still somewhat of an open question. Most languages are approximately context-free, but some have context-sensitive constructs. Others have argued that the nesting-depth of language constructs is limited in practice, making natural languages regular. You could also try the reference desk. —Ruud 18:06, 21 June 2012 (UTC)

 * English is none of these. It (like almost every language spoken by humans) is a Natural Language, while the Hierarchy deals with classification of Formal Languages. The articles on those two do a decent job of explaining the difference. 66.31.201.182 (talk) 16:24, 13 July 2012 (UTC)

 * Chomsky considers all natural languages to be built on the structure of a formal language. So for Chomsky there is no difference between formal langauges and natural languages - except that people speaking formal languages sometimes violate the underltying formal structure by producing performance errors. ·ʍaunus·snunɐw· 16:29, 13 July 2012 (UTC)
 * "Chomsky considers all natural languages to be built on the structure of a formal language" That is a common misconception but it is simply wrong. In fact Chomsky criticizes many philosophers such as Quine for assuming that natural languages are similar to formal languages. He is adamant that this is not the case. For example, in the forward to New Horizons in the Study of Language, Neil Smith writes: "A number of consequences follow from [Chomsky's] naturalistic thesis: there is no justification for the common assumption that natural languages ought to be treated like the invented formal languages of logic or mathematics;"   It is also reflected in the hierarchy. Formal languages such as virtually all computer languages and languages like FOL can be implemented via push down automata because their syntax is context free. In Python the syntax of a statement such as x = x + 1 is context free. There are no equivalents in formal languages to sentences such as "I saw the man on the hill with the telescope" It is also wrong to say "English is none of them". English and all natural languages are the most complex level of the hierarchy: recursively enumerable sets which can only be parsed and generated by Turing machines. That is a core part of Chomsky's theory, that recursion is what separates human language from the languages of other organisms and is what gives human language (and thought) the power for discrete infinity. BTW, an interesting hypothesis (first stated by Randy Gallistal) is that recursion is also what gives humans our number faculty. In a book on how children learn and use language, he demonstrates how the capabilities that seem to be innate in very young children seem to essentially Peano arithmetic which is the formal foundation for all of modern mathematics. --MadScientistX11 (talk) 14:06, 19 December 2023 (UTC)

=Further topics=

Contradiction May Exists...
The following text occurring in the article appears to be a contradiction:

"Note that the set of grammars corresponding to recursive languages is not a member of this hierarchy.

Every regular language is context-free, every context-free language, not containing the empty string, is context-sensitive and every context-sensitive language is recursive and every recursive language is recursively enumerable. These are all proper inclusions, meaning that there exist recursively enumerable languages which are not context-sensitive, context-sensitive languages which are not context-free and context-free languages which are not regular." — Preceding unsigned comment added by 99.245.3.15 (talk) 04:09, 3 March 2013 (UTC)

 * Why? Could you point it out more explicitly? --Zahnradzacken (talk) 10:20, 23 March 2013 (UTC)

Chomsky (1956) does not contain the specified hierarchy
This article claims (and cites) that the hierarchy referred to here as 'the Chomsky Hierarchy' was outlined in Chomsky (1956), 'Three Models for the Description of Language'. Although Chomsky does discuss finite automata in that paper (where they are just one of the three models in a different hierarchy) he makes no attempt to classify them, and indeed, seems to be writing only about so-called Type 2 (push-down) automata, without ever stating as much. The hierarchy he actually discusses in that paper is the hierarchy of 1.) finite state automata; 2.)Phrase Structure Grammars; and 3.) Transformational Grammars.

The 'correct' reference for the hierarchy of automata that is outlined in this article is Chomsky (1959) 'On Certain Formal Properties of Grammar'. However, I am highly dubious that Chomsky deserves credit for _this_ hierarchy: he doesn't cite anyone, thereby creating the impression that perhaps he invented automata theory, but of course he did not. Automata had been much discussed long before 1959. The basic ideas go back at least to the 1930s, with work of Gödel, Church, Turing, Stephen Kleene and Emil Post. Shannon discusses Type 3 (finite state, no stack) automata and their relation to language in his (1949) 'A Mathematical Theory of Communication'.

Chomsky and Miller published a 1959 paper called 'Finite state languages', which I have not yet read but which may shed more light on this matter.

I am not sufficiently educated to know who first distinguished between automata with [Type 2] and without [Type 3] a stack (the main distinction that relevant in Chomsky's work and the only automata distinction discussed in his 1956 paper) but it was almost certainly not Chomsky.

CWestbury (talk) 17:18, 30 July 2013 (UTC)

Feudal languages?
Does the contentions given in this theory have anything to do with the definition: Feudal languages?

See this books by one particular author:

1. March of the evil empires; English versus the feudal languages

2. The SHROUDED SATANISM in FEUDAL LANGUAGES!

3. [https://archive.org/details/Reality_201310 Codes of reality! What is language?]

Or is it a completely different subject matter? — Preceding unsigned comment added by 117.204.86.231 (talk) 19:50, 4 March 2016 (UTC)
 * First, I apologize, I shouldn't be responding because this isn't the place for such discussions but I'm going to anyway: I just looked briefly at the first reference but I'm pretty sure what they are talking about is a completely different topic. Chomsky's hypothesis is that all human languages share certain commonalities, at its core is his hypothesis that recursion is the essence of human language and apart from bird song (where it doesn't seem to play the same role in communication as it does in human language) recursion is unique to human languages. Note: this doesn't imply (as many seem to think it does) that he says humans are "better" than other animals. What I think those books are about are the social issues related to various languages. That is a different topic. Chomsky has talked a bit about some of the political and sociological issues related to language (e.g., that various assertions about some form of a language being "correct" are completely artificial and that is why they are often so hard to enforce) but for the most part, at least as a scientist and linguist, that isn't what he focuses on. --MadScientistX11 (talk) 20:00, 20 December 2023 (UTC)

Chomsky–Schützenberger hierarchy
In the intro it says the hierarchy is sometimes referred to as the Chomsky–Schützenberger hierarchy. Is there a reference for this? I’ve never heard it referred to that way. If there is no reference I’m removing that statement.--MadScientistX11 (talk) 03:36, 24 October 2018 (UTC)

Unreadable
This article is unreadable. It is ironic considering the subject is grammar. It is so terse it lacks a narrative framework; explanations are narrations. This lack of narration is a growing annoying feature of Wikipedia in technical articles. — Preceding unsigned comment added by 99.227.115.169 (talk) 04:53, July 1, 2020 (UTC)

Adding links to § History
I want to add some links but this isn't really my field. Would this be right?

— W.andrea (talk) 19:53, 31 August 2023 (UTC)

title: Talk:Chomsky hierarchy