Indexed grammars are a generalization of context-free grammars in that nonterminals are equipped with lists of flags, or index symbols.The language produced by an indexed grammar is called an indexed language.
In contemporary publications following Hopcroft and Ullman (1979),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[''σ''].[1] Terminal symbols may not be followed by index stacks.For an index stack σ ∈ F* and a string α ∈ (N ∪ T)* of nonterminal and terminal symbols, α[''σ''] denotes the result of attaching [''σ''] to every nonterminal in α; for example if α equals with a,d ∈ T terminal, and nonterminal symbols, then α[''σ''] denotes Using this notation, each production in P has to be of the form
where A, B ∈ N are nonterminal symbols, f ∈ F is an index, σ ∈ F* is a string of index symbols, and α ∈ (N ∪ T)* is a string of nonterminal and terminal symbols. Some authors write ".." instead of "σ" for the index stack in production rules; the rule of type 1, 2, and 3 then reads, and, respectively.
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.
Formally, the relation ⇒ ("direct derivation") is defined on the set (N[''F''<sup>*</sup>]∪T)* of "sentential forms" as follows:
As usual, the derivation relation is defined as the reflexive transitive closure of direct derivation ⇒.The language L(G) = is the set of all strings of terminal symbols derivable from the start symbol.
Historically, the concept of indexed grammars was first introduced by Alfred Aho (1968)[2] 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).[3]
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 :
S[''σ''] | → | S[''fσ''] | T[''fσ''] | → | a T[''σ''] | |
S[''σ''] | → | S[''gσ''] | T[''gσ''] | → | b T[''σ''] | |
S[''σ''] | → | T[''σ''] T[''σ''] T[''σ''] | T[] | → | ε |
A derivation of is then
⇒ ⇒ ⇒ ⇒ ⇒ ⇒ ⇒ ⇒ ⇒ ⇒ ⇒ ⇒ .
As another example, the grammar G = ⟨,,, P, S ⟩ produces the language, where the production set P consists of
S[''σ''] → T[''gσ''] | A[''fσ''] → a A[''σ''] | A[''gσ''] → a | |
T[''σ''] → T[''fσ''] | B[''fσ''] → b B[''σ''] | B[''gσ''] → b | |
T[''σ''] → A[''σ''] B[''σ''] C[''σ''] | C[''fσ''] → c C[''σ''] | C[''gσ''] → c |
⇒ ⇒ ⇒ ⇒ ⇒ ⇒ ⇒ ⇒ ⇒ .
Both example languages are not context-free by the pumping lemma.
Hopcroft and Ullman tend to consider indexed languages as a "natural" class, since they are generated by several formalisms other than indexed grammars, viz.
Hayashi[3] generalized the pumping lemma to indexed grammars.Conversely, Gilman[8] [9] gives a "shrinking lemma" for indexed languages.
Gerald Gazdar has defined a second class, the linear indexed grammars (LIG), by requiring that at most one nonterminal in each production be specified as receiving the stack,[10] 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 α.[11] Also, the direct derivation relation ⇒ is defined similar to above. This new class of grammars defines a strictly smaller class of languages,[12] which belongs to the mildly context-sensitive classes.
The language is generable by an indexed grammar, but not by a linear indexed grammar, while both and are generable by a linear indexed grammar.
If both the original and the modified production rules are admitted, the language class remains the indexed languages.[13]
Letting σ denote an arbitrary sequence of stack symbols, we can define a grammar for the language L = as
S[''σ''] | → | a S[''fσ''] c | |
S[''σ''] | → | T[''σ''] | |
T[''fσ''] | → | T[''σ''] b | |
T[] | → | ε |
To derive the string abc we have the steps:
S[] ⇒ aS[''f'']c ⇒ aT[''f'']c ⇒ aT[]bc ⇒ abc
Similarly:
S[] ⇒ aS[''f'']c ⇒ aaS[''ff'']cc ⇒ aaT[''ff'']cc ⇒ aaT[''f'']bcc ⇒ aaT[]bbcc ⇒ aabbcc
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.[14] LIG rules in general look approximately like
X[\sigma]\to\alphaY[\sigma]\beta
\alpha
\beta
\alpha
\beta
Consider the rule
X[\sigma]\toY[]Z[\sigmaf]
Y[]
Y\prime[\sigma]
Y[]
\sigma
Y\prime[\sigma]
\sigma
Y[]
Y\prime[\sigmaf]\toY\prime[\sigma]
Y\prime[]\toY[]
\{anbncndm|n\geq1,m\geq1\}
S[\sigma]\toT[\sigma]V[]
V[]\tod~|~dV[]
T[\sigma]\toaT[\sigmaf]c~|~U[\sigma]
U[\sigmaf]\tobU[\sigma]
U[]\to\epsilon
V\prime
S[\sigma]\toT[\sigma]V\prime[\sigma]
V\prime[\sigmaf]\toV\prime[\sigma]
V\prime[]\toV[]
V[]\tod~|~dV[]
T[\sigma]\toaT[\sigmaf]c~|~U[\sigma]
U[\sigmaf]\tobU[\sigma]
U[]\to\epsilon
Vijay-Shanker and Weir (1994)[15] demonstrates that Linear Indexed Grammars, Combinatory Categorial Grammars, Tree-adjoining Grammars, and Head Grammars all define the same class of string languages.Their formal definition of linear indexed grammars[16] differs from the above.
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). The latter family can (also) be parsed in polynomial time.[17]
Another form of indexed grammars, introduced by Staudacher (1993), is the class of Distributed Index grammars (DIGs). What distinguishes DIGs from Aho's Indexed Grammars is the propagation of indexes. 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
X[''f''<sub>1</sub>...''f''<sub>''i''</sub>''f''<sub>''i''+1</sub>...''f''<sub>''n''</sub>] → α Y[f<sub>1</sub>...''f''<sub>''i''</sub>] β Z[''f''<sub>''i''+1</sub>...''f''<sub>''n''</sub>] γWhere α, β, and γ are arbitrary terminal strings. For a ternarily distributing string:
X[''f''<sub>1</sub>...''f''<sub>''i''</sub>''f''<sub>''i''+1</sub>...''f''<sub>''j''</sub>''f''<sub>''j''+1</sub>...''f''<sub>''n''</sub>] → α Y[f<sub>1</sub>...''f''<sub>''i''</sub>] β Z[''f''<sub>''i''+1</sub>...''f''<sub>''j''</sub>] γ W[''f''<sub>''j''+1</sub>...''f''<sub>''n''</sub>] ηAnd so forth for higher numbers of non-terminals in the right hand side of the rewrite rule. In general, if there are m non-terminals in the right hand side of a rewrite rule, the stack is partitioned m ways and distributed amongst the new non-terminals. Notice that there is a special case where a partition is empty, which effectively makes the rule a LIG rule. The Distributed Index languages are therefore a superset of the Linearly Indexed languages.