In contemporary publications following Hopcroft and Ullman (1979), [2] an indexed grammar is formally defined a 5-tuple G = ⟨N,T,F,P,S⟩ where In productions as well as in derivations of indexed grammars, a string ("stack") σ ∈ F* of index symbols is attached to every nonterminal symbol A ∈ N, denoted by A[σ].
[note 1] Terminal symbols may not be followed by index stacks.
Derivations are similar to those in a context-free grammar except for the index stack attached to each nonterminal symbol.
When a production like e.g. A[σ] → B[σ]C[σ] is applied, the index stack of A is copied to both B and C. Moreover, a rule can push an index symbol onto the stack, or pop its "topmost" (i.e., leftmost) index symbol.
Historically, the concept of indexed grammars was first introduced by Alfred Aho (1968)[3] using a different formalism.
Aho defined an indexed grammar to be a 5-tuple (N,T,F,P,S) where Direct derivations were as follows: This formalism is e.g. used by Hayashi (1973, p. 65-66).
[4] In practice, stacks of indices can count and remember what rules were applied and in which order.
For example, indexed grammars can describe the context-sensitive language of word triples { www : w ∈ {a,b}* }: A derivation of abbabbabb is then As another example, the grammar G = ⟨ {S,T,A,B,C}, {a,b,c}, {f,g}, P, S ⟩ produces the language { anbncn: n ≥ 1 }, where the production set P consists of An example derivation is Both example languages are not context-free by the pumping lemma.
[5] Hayashi[4] generalized the pumping lemma to indexed grammars.
Conversely, Gilman[10][11] gives a "shrinking lemma" for indexed languages.
Gerald Gazdar has defined a second class, the linear indexed grammars (LIG),[14] by requiring that at most one nonterminal in each production be specified as receiving the stack,[note 2] whereas in an ordinary indexed grammar, all nonterminals receive copies of the stack.
Formally, a linear indexed grammar is defined similar to an ordinary indexed grammar, but the production's form requirements are modified to: where A, B, f, σ, α are used as above, and β ∈ (N ∪ T)* is a string of nonterminal and terminal symbols like α.
[note 3] Also, the direct derivation relation ⇒ is defined similar to above.
[16] Letting σ denote an arbitrary sequence of stack symbols, we can define a grammar for the language L = {an bn cn | n ≥ 1 }[note 4] as To derive the string abc we have the steps: Similarly: The linearly indexed languages are a subset of the indexed languages, and thus all LIGs can be recoded as IGs, making the LIGs strictly less powerful than the IGs.
A conversion from a LIG to an IG is relatively simple.
, changing the grammar to: Each rule now fits the definition of an IG, in which all the non-terminals in the right hand side of a rewrite rule receive a copy of the rewritten symbol's stack.
Their formal definition of linear indexed grammars[19] differs from the above.
[clarification needed] LIGs (and their weakly equivalents) are strictly less expressive (meaning they generate a proper subset) than the languages generated by another family of weakly equivalent formalism, which include: LCFRS, MCTAG, MCFG and minimalist grammars (MGs).
Unlike Aho's IGs, which distribute the whole symbol stack to all non-terminals during a rewrite operation, DIGs divide the stack into substacks and distributes the substacks to selected non-terminals.
The general rule schema for a binarily distributing rule of DIG is the form Where α, β, and γ are arbitrary terminal strings.
For a ternarily distributing string: And so forth for higher numbers of non-terminals in the right hand side of the rewrite rule.