View source for Indexed grammar

'''Indexed grammars''' are a generalization of [[context-free grammar]]s in that [[nonterminal]]s are equipped with lists of ''flags'', or ''index symbols''.
The language produced by an indexed grammar is called an '''[[indexed language]]'''.

==Definition==

===Modern definition by Hopcroft and Ullman===

<!---supplemented from talk page # Definition by Hopcroft+Ullman 1979--->
In contemporary publications following Hopcroft and Ullman (1979),
{{refn|Hopcroft and Ullman (1979),<ref name=Hopcroft_and_Ullman>{{cite book | last = Hopcroft | author-link = John Hopcroft | first = John E. | author2 = Jeffrey D. Ullman | title = Introduction to Automata Theory, Languages, and Computation | year = 1979 | publisher = Addison-Wesley | isbn = 978-0-201-02988-8| title-link = Introduction to Automata Theory, Languages, and Computation | author2-link = Jeffrey D. Ullman }}</ref> Sect.14.3, p.389-390. This section is omitted in the 2nd edition 2003.}}
an indexed grammar is formally defined a 5-tuple ''G'' = ⟨''N'',''T'',''F'',''P'',''S''⟩ where

* ''N'' is a set of variables or [[Nonterminal|nonterminal symbols]],
* ''T'' is a set ("[[alphabet (formal languages)|alphabet]]") of terminal symbols,
* ''F'' is a set of so-called ''index symbols'', or ''indices'',
* ''S'' ∈ ''N'' is the ''[[start symbol (formal languages)|start symbol]]'', and
* ''P'' is a finite set of ''[[Production (formal languages)|productions]]''.

In productions as well as in derivations of indexed grammars, a string ("stack") ''σ'' ∈ ''F''[[Kleene star|<sup>*</sup>]] of index symbols is attached to every nonterminal symbol ''A'' ∈ ''N'', denoted by ''A''[''σ''].<ref group=note>"[" and "]" are meta symbols to indicate the stack.</ref>
Terminal symbols may not be followed by index stacks.
For an index stack ''σ'' ∈ ''F''<sup>*</sup> and a string ''α'' ∈ (''N'' ∪ ''T'')<sup>*</sup> of nonterminal and terminal symbols, ''α''[''σ''] denotes the result of attaching [''σ''] to every nonterminal in ''α''; for example if ''α'' equals {{math|''a'' ''B'' ''C'' ''d'' ''E''}} with ''a'',''d'' ∈ ''T'' terminal, and {{math|''B'',''C'',''E'' ∈ ''N''}} nonterminal symbols, then ''α''[''σ''] denotes {{math|''a'' ''B''[''σ''] ''C''[''σ''] ''d'' ''E''[''σ''].}}
Using this notation, each production in ''P'' has to be of the form

# ''A''[σ] → α[σ],
# ''A''[σ] → ''B''[''f''σ], or
# ''A''[''f''σ] → α[σ],

where ''A'', ''B'' ∈ ''N'' are nonterminal symbols, ''f'' ∈ ''F'' is an index, ''σ'' ∈ ''F''<sup>*</sup> is a string of index symbols, and ''α'' ∈ (''N'' ∪ ''T'')<sup>*</sup> 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 {{math|''A''[..]→''α''[..], &nbsp; ''A''[..]→''B''[''f''..]}}, and {{math|''A''[''f''..]→''α''[..]}}, respectively.

Derivations are similar to those in a [[context-free grammar#Rule application|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'')<sup>*</sup> of "sentential forms" as follows:
#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.
#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.
#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 {{overset|[[reflexive transitive closure|&lowast;]]|⇒}} is defined as the [[reflexive transitive closure]] of direct derivation ⇒.
The language ''L''(''G'') = { ''w'' ∈ ''T''<sup>*</sup>: ''S''  {{overset|&lowast;|⇒}} ''w'' } is the set of all strings of terminal symbols derivable from the start symbol.
<!---contents of former section "Description"--->
<!---now contained in the informal description of the derivation relation and the note about meta symbols--->

===Original definition by Aho===

<!---former section "Definition"--->
Historically, the concept of indexed grammars was first introduced by [[Alfred Aho]] (1968)<ref name="aho1968">{{cite journal | last = Aho | author-link = Alfred Aho | first = Alfred | year = 1968 | title = Indexed grammars—an extension of context-free grammars | journal = [[Journal of the ACM]] | volume = 15 | issue = 4 | pages = 647–671 | doi = 10.1145/321479.321488 | s2cid = 9539666 | doi-access = free }}</ref> using a different formalism.
Aho defined an indexed grammar to be a 5-tuple (''N'',''T'',''F'',''P'',''S'') where
# ''N'' is a finite [[alphabet]] of variables or [[Nonterminal|nonterminal symbols]]
# ''T'' is a finite alphabet of terminal symbols
# ''F'' ⊆ [[power set|2]]<sup>''N'' × (''N'' ∪ ''T'')[[Kleene star|<sup>*</sup>]]</sup> is the finite set of so-called ''flags'' (each flag is itself a set of so-called ''index productions'')
# ''P'' ⊆ ''N'' × (''NF''<sup>*</sup> ∪ ''T'')<sup>*</sup> is the finite set of ''[[Production (computer science)|productions]]''
# ''S'' ∈ ''N'' is the ''start symbol''

Direct derivations were as follows:

* A production ''p'' = (''A'' → ''X''<sub>1</sub>''η''<sub>1</sub>…''X''<sub>''k''</sub>''η''<sub>''k''</sub>) from ''P'' matches a nonterminal ''A'' ∈ ''N'' followed by its (possibly empty) string of flags ''ζ'' ∈ ''F''<sup>*</sup>. In context, ''γ'' ''Aζ'' ''δ'', via ''p'', derives to ''γ'' ''X''<sub>1</sub>''θ''<sub>1</sub>…''X''<sub>''k''</sub>''θ''<sub>''k''</sub> ''δ'', where ''θ''<sub>''i''</sub> = ''η''<sub>''i''</sub>''ζ'' if ''X''<sub>''i''</sub> 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''<sub>1</sub>…''X''<sub>''k''</sub>) ∈ ''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''<sub>1</sub>''θ''<sub>1</sub>…''X''<sub>''k''</sub>''θ''<sub>''k''</sub> ''δ'', where ''θ''<sub>''i''</sub> is the empty word when ''X''<sub>''i''</sub> 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.&nbsp;65-66).<ref name="Hayashi.1973">{{cite journal | url=http://www.ems-ph.org/journals/show_pdf.php?issn=0034-5318&vol=9&iss=1&rank=3| doi=10.2977/prims/1195192738| title=On derivation trees of indexed grammars: An extension of the ''uvwxy''-theorem| journal=Publications of the Research Institute for Mathematical Sciences| volume=9| pages=61–92| year=1973| last1=Hayashi| first1=Takeshi| doi-access=free}}</ref>

==Examples==

<!---former section "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'' ∈ {''a'',''b''}<sup>*</sup> }:

:{|
|-
| ''S''[''σ''] || → || ''S''[''fσ'']
| ''T''[''fσ''] || → || ''a'' ''T''[''σ'']
|-
| ''S''[''σ''] || → || ''S''[''gσ'']
| ''T''[''gσ''] || → || ''b'' ''T''[''σ'']
|-
| ''S''[''σ''] || → || ''T''[''σ''] ''T''[''σ''] ''T''[''σ''] &nbsp; &nbsp; &nbsp; 
| ''T''[] || → || ''ε''
|}

A derivation of ''{{not a typo|abbabbabb}}'' is then

:{{math|size=100%|''S''[]}} ⇒ {{math|size=100%|''S''[''g'']}} ⇒ {{math|size=100%|''S''[''gg'']}} ⇒ {{math|size=100%|''S''[''fgg'']}} ⇒ {{math|size=100%|''T''[''fgg''] ''T''[''fgg''] ''T''[''fgg'']}} ⇒ {{math|size=100%|''a'' ''T''[''gg''] ''T''[''fgg''] ''T''[''fgg'']}} ⇒ {{math|size=100%|''ab'' ''T''[''g''] ''T''[''fgg''] ''T''[''fgg'']}} ⇒ {{math|size=100%|''abb'' ''T''[] ''T''[''fgg''] ''T''[''fgg'']}} ⇒ {{math|size=100%|''abb'' ''T''[''fgg''] ''T''[''fgg'']}} ⇒ {{math|size=100%|...}} ⇒ {{math|size=100%|''abb'' ''abb'' ''T''[''fgg'']}} ⇒ {{math|size=100%|...}} ⇒ {{math|size=100%|''abb'' ''abb'' ''abb''}}.

<!---supplemented from talk page # Example by Hopcroft+Ullman 1979--->
As another example, the grammar ''G'' = ⟨ {''S'',''T'',''A'',''B'',''C''}, {''a'',''b'',''c''}, {''f'',''g''}, ''P'', ''S'' ⟩ produces the language { ''a''<sup>''n''</sup>''b''<sup>''n''</sup>''c''<sup>''n''</sup>: ''n'' ≥ 1 }, 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''[''σ''] &nbsp; &nbsp; &nbsp; || ''C''[''fσ''] → ''c'' ''C''[''σ''] &nbsp; &nbsp; &nbsp; || ''C''[''gσ''] → ''c''
|}
An example derivation is
:{{math|size=100%|''S''[]}} ⇒ {{math|size=100%|''T''[''g'']}} ⇒ {{math|size=100%|''T''[''fg'']}} ⇒ {{math|size=100%|''A''[''fg''] ''B''[''fg''] ''C''[''fg'']}} ⇒ {{math|size=100%|''aA''[''g''] ''B''[''fg''] ''C''[''fg'']}} ⇒ {{math|size=100%|''aA''[''g''] ''bB''[''g''] ''C''[''fg'']}} ⇒ {{math|size=100%|''aA''[''g''] ''bB''[''g''] ''cC''[''g'']}} ⇒ {{math|size=100%|''aa'' ''bB''[''g''] ''cC''[''g'']}} ⇒ {{math|size=100%|''aa'' ''bb'' ''cC''[''g'']}} ⇒ {{math|size=100%|''aa'' ''bb'' ''cc''}}.

Both example languages are not context-free by the [[Pumping lemma for context-free languages#Usage of the lemma|pumping lemma]].

==Properties==

<!---former contents of section "Description" (added 3 Feb 2014)--->
[[John Hopcroft|Hopcroft]] and [[Jeffrey Ullman|Ullman]] tend to consider indexed languages as a "natural" class, since they are generated by several formalisms other than indexed grammars, viz.{{refn|Hopcroft and Ullman (1979),<ref name=Hopcroft_and_Ullman/> Bibliographic notes, p.394-395}}
* [[Alfred Aho|Aho]]'s one-way [[nested stack automata]]<ref>{{cite journal| author=Alfred Aho| title=Nested Stack Automata| journal=Journal of the ACM| year=1969| volume=16| number=3| pages=383–406| doi=10.1145/321526.321529| s2cid=685569| doi-access=free}}</ref>
* [[Michael J. Fischer|Fischer]]'s macro grammars<ref>{{cite book| author=Michael J. Fischer| chapter=Grammars with Macro-Like Productions| title=Proc. 9th Ann. IEEE Symp. on Switching and Automata Theory (SWAT)| year=1968| pages=131–142| doi=10.1109/SWAT.1968.12}}</ref>
* [[Sheila Greibach|Greibach]]'s automata with stacks of stacks<ref>{{cite journal| author=Sheila A. Greibach| title=Full AFL's and Nested Iterated Substitution| journal=Information and Control| year=1970| volume=16| number=1| pages=7–35| doi=10.1016/s0019-9958(70)80039-0| doi-access=free}}</ref>
* [[Tom Maibaum|Maibaum]]'s algebraic characterization<ref>{{cite journal| author=T.S.E. Maibaum| title=A Generalized Approach to Formal Languages| journal=Journal of Computer and System Sciences| year=1974| volume=8| number=3| pages=409–439| doi=10.1016/s0022-0000(74)80031-0| doi-access=free}}</ref>

Hayashi<ref name="Hayashi.1973"/> generalized the [[Pumping lemma for context-free languages|pumping lemma]] to indexed grammars.
Conversely, Gilman<ref>{{cite journal| author=Robert H. Gilman| title=A Shrinking Lemma for Indexed Languages| journal=Theoretical Computer Science| year=1996| volume=163| issue=1–2| pages=277–281| doi=10.1016/0304-3975(96)00244-7| arxiv=math/9509205| s2cid=14479068}}</ref><ref>{{cite arXiv| author=Robert H. Gilman| title=A Shrinking Lemma for Indexed Languages|date=Sep 1995| eprint=math/9509205}}</ref> gives a "shrinking lemma" for indexed languages.

==Linear indexed grammars==

[[Gerald Gazdar]] has defined a second class, the '''linear indexed grammars''' ('''LIG'''),{{refn|According to Staudacher (1993, p.361 left, Sect.2.2),<ref name="staudacher1993"/> the name "linear indexed grammars" wasn't used in Gazdar's 1988 paper, but appeared later, e.g. in Weir and Joshi (1988).<ref>{{cite book|author1=David J. Weir |author2=Aravind K. Joshi | chapter=Combinatory Categorial Grammars: Generative Power and Relationship to Linear Context-Free Rewriting Systems| title=Proc. 26th Meeting Assoc. Comput. Ling.| year=1988| pages=278–285| chapter-url=http://acl.ldc.upenn.edu/P/P88/P88-1034.pdf?origin=publication_detail}}</ref>}} by requiring that at most one nonterminal in each production be specified as receiving the stack,<ref group=note>all other nonterminals receive an empty stack</ref>
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:

# ''A''[''σ''] → ''α''[] ''B''[''σ''] ''β''[],
# ''A''[''σ''] → ''α''[] ''B''[''fσ''] ''β''[],
# ''A''[''fσ''] → ''α''[] ''B''[''σ''] ''β''[],

where ''A'', ''B'', ''f'', ''σ'', ''α'' are used as [[#Modern definition by Hopcroft and Ullman|above]], and ''β'' ∈ (''N'' ∪ ''T'')<sup>*</sup> is a string of nonterminal and terminal symbols like ''α''.<ref group=note name="Gazdars def">In order to generate any string at all, some productions must be admitted having no nonterminal symbol on their right hand side. However, Gazdar didn't discuss this issue.</ref> Also, the direct derivation relation ⇒ is defined similar to above. This new class of grammars defines a strictly smaller class of languages,<ref name="gazdar1998">{{cite book | chapter=Applicability of Indexed Grammars to Natural Languages | year=1988 | last=Gazdar | first=Gerald | title=Natural Language Parsing and Linguistic Theories | editor=U. Reyle and C. Rohrer | pages=69–94 | publisher=D. Reidel Publishing Company | isbn=978-1-55608-055-5 | series=Studies in linguistics and philosophy |volume=35}}</ref>  
which belongs to the [[mildly context-sensitive language|mildly context-sensitive]] classes.

The language { ''www'' : ''w'' ∈ {''a'',''b''}<sup>*</sup> } is generable by an indexed grammar, but not by a linear indexed grammar, while both { ''ww'' : ''w'' ∈ {''a'',''b''}<sup>*</sup> } and { ''a''<sup>''n''</sup> ''b''<sup>''n''</sup> ''c''<sup>''n''</sup> : n ≥ 1 } 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.<ref>Gazdar (1988), Appendix, p.89</ref>

===Example===

Letting σ denote an arbitrary sequence of stack symbols, we can define a grammar for the language ''L'' = {''a''<sup>''n''</sup> ''b''<sup>''n''</sup> ''c''<sup>''n''</sup> | ''n'' ≥ 1 }{{refn|Cf. the properly indexed grammar for the same language given [[#Examples|above]]. The last rule, viz. ''T''[]→ε, of the linear indexed grammar doesn't conform to Gazdar's definition in a strict sense, cf. <ref group=note name="Gazdars def"/>|group=note}} 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''

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

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

: <math>Y^{\prime}[\sigma f] \to Y^{\prime}[\sigma]</math>

: <math>Y^{\prime}[] \to Y[]</math>
We can apply this in general to derive an IG from an LIG. So for example if the LIG for the language <math>\{a^n b^n c^n d^m | n \geq 1, m \geq 1\}</math> is as follows:

: <math>S[\sigma] \to T[\sigma]V[]</math>

: <math>V[] \to d ~|~ dV[]</math>

: <math>T[\sigma] \to aT[\sigma f]c ~|~ U[\sigma]</math>

: <math>U[\sigma f] \to bU[\sigma]</math>

: <math>U[] \to \epsilon</math>
The sentential rule here is not an IG rule, but using the above conversion algorithm, we can define new rules for <math>V^{\prime}</math>, changing the grammar to:

: <math>S[\sigma] \to T[\sigma]V^{\prime}[\sigma]</math>

: <math>V^{\prime}[\sigma f] \to V^{\prime}[\sigma]</math>

: <math>V^{\prime}[] \to V[]</math>

: <math>V[] \to d ~|~ dV[]</math>

: <math>T[\sigma] \to aT[\sigma f]c ~|~ U[\sigma]</math>

: <math>U[\sigma f] \to bU[\sigma]</math>

: <math>U[] \to \epsilon</math>
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.

===Relation to other formalisms===

Vijay-Shanker and Weir (1994)<ref name="vijayshankarAndWeir1995">{{cite journal |author=Vijay-Shanker, K. |author2=Weir, David J. 1994. |title=The Equivalence of Four Extensions of Context-Free Grammars |journal=Mathematical Systems Theory |volume=27 |issue=6 |pages=511–546 |url=http://citeseer.ist.psu.edu/viewdoc/download?doi=10.1.1.52.4044&rep=rep1&type=pdf |doi=10.1007/bf01191624|year=1994 |s2cid=12336597 }}</ref> demonstrates that Linear Indexed Grammars, [[Combinatory categorial grammar|Combinatory Categorial Grammars]], [[Tree-adjoining grammar|Tree-adjoining Grammars]], and [[Head grammar|Head Grammars]] all define the same class of string languages.
Their formal definition of linear indexed grammars<ref>p.517-518</ref> differs from the [[#Linear indexed grammars|above]].{{clarify|date=August 2014}}

LIGs (and their [[Equivalence (formal languages)|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 grammar]]s (MGs). The latter family can (also) be parsed in [[polynomial time]].<ref name="BenthemMeulen2010">{{cite book|author1=Johan F.A.K. van Benthem|author2=Alice ter Meulen|author2-link=Alice ter Meulen|title=Handbook of Logic and Language|url=https://books.google.com/books?id=K7yJLmZCbFUC&pg=PA404|year=2010|publisher=Elsevier|isbn=978-0-444-53727-0|page=404|edition=2nd}}</ref>

==Distributed index grammars==
Another form of indexed grammars, introduced by Staudacher (1993),<ref name="staudacher1993">{{citation |author=Staudacher, Peter |year=1993 |contribution=New frontiers beyond context-freeness: DI-grammars (DIGs) and DI-automata. | title=Sixth Conference of the European Chapter of the Association for Computational Linguistics (EACL '93) |contribution-url=https://aclanthology.org/E93-1042.pdf |pages=358–367 }}</ref> 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.

==See also==
* [[Chomsky hierarchy]]

==Notes==
{{Reflist|group=note}}

==References==
{{Reflist}}

==External links==
* [https://web.archive.org/web/20070311042935/http://www.cogs.susx.ac.uk/research/nlp/gazdar/nlp-in-prolog/ch04/chapter-04-sh-1.6.3.html "NLP in Prolog" chapter on indexed grammars and languages]

{{Formal languages and grammars}}

[[Category:Formal languages]]
[[Category:Grammar frameworks]]