Indexed grammar

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

• N is a set of variables or nonterminal symbols,
• T is a set ("alphabet") of terminal symbols,
• F is a set of so-called index symbols, or indices,
• S ∈ N is the start symbol, and
• P is a finite set of productions.

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. 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 a B C d E with a,d ∈ T terminal, and B,C,E ∈ N nonterminal symbols, then α[σ] denotes a B[σ] C[σ] d E[σ]. Using this notation, each production in P has to be of the form

1. A[σ] → α[σ],
2. A[σ] → B[fσ], or
3. A[fσ] → α[σ],

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 A[..]→α[..],   A[..]→B[f..], and A[f..]→α[..], 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^*]∪T)^* of "sentential forms" as follows:

1. If A[σ] → α[σ] is a production of type 1, then β A[φ] γ ⇒ β α[φ] γ, using the above definition. That is, the rule's left hand side's index stack φ is copied to each nonterminal of the right hand side.
2. If A[σ] → B[fσ] is a production of type 2, then β A[φ] γ ⇒ β B[fφ] γ. That is, the right hand side's index stack is obtained from the left hand side's stack φ by pushing f onto it.
3. If A[fσ] → α[σ] is a production of type 3, then β A[fφ] γ ⇒ β α[φ] γ, using again the definition of α[σ]. That is, the first index f is popped from the left hand side's stack, which is then distributed to each nonterminal of the right hand side.

As usual, the derivation relation ∗⇒ is defined as the reflexive transitive closure of direct derivation ⇒. The language L(G) = { w ∈ T^*: S ∗⇒ w } 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)[3] using a different formalism. Aho defined an indexed grammar to be a 5-tuple (N,T,F,P,S) where

1. N is a finite alphabet of variables or nonterminal symbols
2. T is a finite alphabet of terminal symbols
3. F ⊆ 2^{N × (N ∪ T)*} is the finite set of so-called flags (each flag is itself a set of so-called index productions)
4. P ⊆ N × (NF^* ∪ T)^* is the finite set of productions
5. S ∈ N is the start symbol

Direct derivations were as follows:

• A production p = (A → X₁η₁…X_kη_k) from P matches a nonterminal A ∈ N followed by its (possibly empty) string of flags ζ ∈ F^*. In context, γ Aζ δ, via p, derives to γ X₁θ₁…X_kθ_k δ, where θ_i = η_iζ if X_i was a nonterminal and the empty word otherwise. The old flags of A are therefore copied to each new nonterminal produced by p. Each such production can be simulated by appropriate productions of type 1 and 2 in the Hopcroft/Ullman formalism.
• An index production p = (A → X₁…X_k) ∈ f matches Afζ (the flag f it comes from must match the first symbol following the nonterminal A) and copies the remaining index string ζ to each new nonterminal: γ Afζ δ derives to γ X₁θ₁…X_kθ_k δ, where θ_i is the empty word when X_i is a terminal and ζ when it is a nonterminal. Each such production corresponds to a production of type 3 in the Hopcroft/Ullman formalism.

This formalism is e.g. used by Hayashi (1973, p. 65-66).[4]

Letting σ denote an arbitrary sequence of stack symbols, we can define a grammar for the language L = {aⁿ bⁿ cⁿ | n ≥ 1 }[note 4] 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.[17] LIG rules in general look approximately like ${\displaystyle X[\sigma ]\to \alpha Y[\sigma ]\beta }$, modulo the push/pop part of a rewrite rule. The symbols ${\displaystyle \alpha }$ and ${\displaystyle \beta }$ represent strings of terminal and/or non-terminal symbols, and any non-terminal symbol in either must have an empty stack, by the definition of a LIG. This is, of course, counter to how IGs are defined: in an IG, the non-terminals whose stacks are not being pushed to or popped from must have exactly the same stack as the rewritten non-terminal. Thus, somehow, we need to have non-terminals in ${\displaystyle \alpha }$ and ${\displaystyle \beta }$ which, despite having non-empty stacks, behave as if they had empty stacks.

Consider the rule ${\displaystyle X[\sigma ]\to Y[]Z[\sigma f]}$ as an example case. In converting this to an IG, the replacement for ${\displaystyle Y[]}$ must be some ${\displaystyle Y^{\prime }[\sigma ]}$ that behaves exactly like ${\displaystyle Y[]}$ regardless of what ${\displaystyle \sigma }$ is. To achieve this, we can simply have a pair of rules that takes any ${\displaystyle Y^{\prime }[\sigma ]}$ where ${\displaystyle \sigma }$ is not empty, and pops symbols from the stack. Then, when the stack is empty, it can be rewritten as ${\displaystyle Y[]}$.

${\displaystyle Y^{\prime }[\sigma f]\to Y^{\prime }[\sigma ]}$

${\displaystyle Y^{\prime }[]\to Y[]}$

We can apply this in general to derive an IG from an LIG. So for example if the LIG for the language ${\displaystyle \{a^{n}b^{n}c^{n}d^{m}|n\geq 1,m\geq 1\}}$ is as follows:

${\displaystyle S[\sigma ]\to T[\sigma ]V[]}$

${\displaystyle V[]\to d~|~dV[]}$

${\displaystyle T[\sigma ]\to aT[\sigma f]c~|~U[\sigma ]}$

${\displaystyle U[\sigma f]\to bU[\sigma ]}$

${\displaystyle U[]\to \epsilon }$

The sentential rule here is not an IG rule, but using the above conversion algorithm, we can define new rules for ${\displaystyle V^{\prime }}$, changing the grammar to:

${\displaystyle S[\sigma ]\to T[\sigma ]V^{\prime }[\sigma ]}$

${\displaystyle V^{\prime }[\sigma f]\to V^{\prime }[\sigma ]}$

${\displaystyle V^{\prime }[]\to V[]}$

${\displaystyle V[]\to d~|~dV[]}$

${\displaystyle T[\sigma ]\to aT[\sigma f]c~|~U[\sigma ]}$

${\displaystyle U[\sigma f]\to bU[\sigma ]}$

${\displaystyle U[]\to \epsilon }$

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. The indexed grammars are therefore able to describe all the languages that linearly indexed grammars can describe.

Vijay-Shanker and Weir (1994)[18] 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[19] 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.[20]