Indexed grammar

An indexed grammar is a formal grammar which describes indexed languages. They have three disjoint sets of symbols: the usual terminals and nonterminals, as well as index symbols, which appear only in intermediate derivation steps on a stack associated with the non-terminals of that step.

Definition

Formally, an indexed grammar is 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 \subseteq 2^{N \times (N \cup T)^\ast}$ is the finite set of so-called flags (each flag is itself a set of so-called index productions)
4. $P \subseteq N \times (NF^\ast \cup T)^\ast$ is the finite set of productions
5. $S \in N$ is the sentence symbol

Direct derivations are as follows:

• A production $p = (A, X_1\eta_1\dots X_k\eta_k)$ from $P$ matches a nonterminal $A \in N$ followed by its (possibly empty) string of flags $\zeta \in F^\ast$. In context, $\gamma A \zeta \delta$, via $p$, derives to $\gamma X_1 \theta_1 \dots X_k\theta_k \delta$, where $\theta_i = \eta_i\zeta$ 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$
• An index production $p = (A, X_1\dots X_k) \in f$ matches $Af\zeta$ (the flag it comes from must match the first symbol following the nonterminal) and copies the remaining index string $\zeta$ to each new nonterminal: $\gamma A f \zeta \delta$ derives to $\gamma X_1 \theta_1\zeta \dots X_k\theta_k\zeta \delta$, where $\theta_i$ is the empty word when $X_i$ is a nonterminal and $\zeta$ otherwise.

Description

A string with a non-terminal symbol $X$ with some index symbols $abc$ on its stack, can be denoted as $\alpha X[abc] \beta$ (using the [ and ] as metasymbols to denote the stack). In an indexed grammar, the application of a production rule such as $X[\sigma] \to \gamma Y[\sigma] \delta Z[\sigma] \eta$ would rewrite the string by replacing $X[abc]$ with $\gamma Y[abc] \delta Z[abc] \eta$, which copies the stack symbols $abc$ from $X$ to each non-terminal in its replacement — $Y$ and $Z$ in this case. In the process, a symbol can be pushed to, or popped from, the stack before the stack is copied to the introduced non-terminals, which would be specified in the rule for the rewriting operation.

Example

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 \in \{a,b\}^{*} \}$:

$S[\sigma] \to S[\sigma f] ~|~ S[\sigma g]$

$S[\sigma] \to T[\sigma]T[\sigma]T[\sigma]$

$T[\sigma f] \to T[\sigma]a$

$T[\sigma g] \to T[\sigma]b$

$T[] \to \epsilon$

The derivation of $abbabbabb$ is then

$S[] \to S[f] \to S[fg] \to S[fgg] \to T[fgg]T[fgg]T[fgg]$

$\to T[fg]bT[fgg]T[fgg] \to T[f]bbT[fgg]T[fgg] \to T[]abbT[fgg]T[fgg]$

$\to abbT[fgg]T[fgg] \to \dotsb \to abbabbT[fgg] \to abbabbabb$

Linear indexed grammars

Gerald Gazdar has defined a second class, the linear indexed grammars, by requiring that at most one nonterminal in each production be specified as receiving the stack, whereas in a normal indexed grammar, all nonterminals receive copies of the stack. He showed that this new class of grammars defines a strictly smaller class of languages, the mildly context sensitive languages. Membership in a linear indexed grammar can be decided in polynomial time.

The language $\{ www : w \in \{a,b\}^{*}\}$ is generable by an indexed grammar, but not by a linear indexed grammar, while $\{a^n b^n c^n | n \geq 1\}$ is generable by a linear indexed grammar.

Example

Letting $\sigma$ denote an arbitrary collection of stack symbols, we can define a grammar for the language $L = \{a^n b^n c^n | n \geq 1\}$ as

$S[\sigma] \to aS[\sigma f]c$

$S[\sigma] \to T[\sigma]$

$T[\sigma f] \to T[\sigma]b$

$T[] \to \epsilon$

To derive the string $abc$ we have the steps $S[] \to aS[f]c \to aT[f]c \to aT[]bc \to abc$.

Similarly, for $aabbcc$: $S[] \to aS[f]c \to aaS[ff]cc \to aaT[ff]cc \to aaT[f]bcc \to aaT[]bbcc \to aabbcc$.

Computational Power

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. LIG rules in general look approximately like $X[\sigma] \to \alpha Y[\sigma] \beta$, modulo the push/pop part of a rewrite rule. The symbols $\alpha$ and $\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 $\alpha$ and $\beta$ which, despite having non-empty stacks, behave as if they had empty stacks.

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

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

$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 $\{a^n b^n c^n d^m | n \geq 1, m \geq 1\}$ is as follows:

$S[\sigma] \to T[\sigma]V[]$

$V[] \to d ~|~ dV[]$

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

$U[\sigma f] \to bU[\sigma]$

$U[] \to \epsilon$

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

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

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

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

$V[] \to d ~|~ dV[]$

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

$U[\sigma f] \to bU[\sigma]$

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

Equivalencies

Vijay-Shanker and Weir (1994) demonstrates that Linear Indexed Grammars, Combinatory Categorial Grammars, Tree-adjoining Grammars, and Head Grammars are weakly equivalent formalisms, in that they all define the same string languages.

Distributed Index (DI) grammars

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_1 \dotso f_i f_j \dotso f_n] \to \alpha Y[f_1 \dotso f_i] \beta Z[f_j \dotso f_n] \gamma$

Where $\alpha$, $\beta$, and $\gamma$ are arbitrary terminal strings. For a ternarily distributing string:

$X[f_1 \dotso f_i f_j \dotso f_k f_l \dotso f_n] \to \alpha Y[f_1 \dotso f_i] \beta Z[f_j \dotso f_k] \gamma W[f_l \dotso f_n] \eta$

And so forth for higher numbers of non-terminals in the right hand side of the rewrite rule. In general, if there are $N$ non-terminals in the right hand side of a rewrite rule, the stack is partitioned $N$ 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.

See also

• Chomsky hierarchy
• Indexed language

External links

• "NLP in Prolog" chapter on indexed grammars and languages