Global index grammars (GIGs) are a class of grammars introduced in Castaño (2004) in order to model a number of phenomena, including natural language grammar and genome grammar. The easiest description of GIGs is by comparison to Indexed grammars. Whereas in indexed grammars, a stack of indices is associated with each nonterminal symbol, and can vary from one to another depending on the course of the derivation, in a GIG, there is a single global index stack that is manipulated in the course of the derivation (which is strictly leftmost for any rewrite operation that pushes a symbol to the stack). Because of the existence of a global stack, a GIG derivation is considered complete when there are no non-terminal symbols left to be rewritten, and the stack is empty.
Rule Description GIG rules come in essentially four forms: rules that do something unconditionally, rules that do something conditioned on the topmost symbol of the stack, rules that push to the stack, and rules that pop from the stack. We can notate these in turn as:
where f is any index symbol, α is any string of terminals and/or non-terminal symbols, and x is a terminal is a terminal symbol. Because occasionally a rewrite rule might need to be conditioned on the stack being in some sense empty, the symbol # is used as the bottom-most stack symbol, meaning an "empty" stack contains exactly one symbol, #. The third rule form, the push rule, should be pointed out, as it differs from the pop rule in requiring that all push operations introduce at least one new terminal symbol to the derivation string. Without this constraint, the class of grammars would be Type-0 and thus Turing Complete.
Example For this example, we will denote steps in the derivation by placing the derivation string over a stack, as in a b X d [ f f g ] {\displaystyle {\frac {abXd}{[ffg]}}} . GIGs (but not trGIGs as below) can generate the non-indexed language { w w + : w ∈ { a , b } ∗ } {\displaystyle \{ww^{+}:w\in \{a,b\}^{*}\}} using the following grammar:
S → A S | B S | C | ϵ {\displaystyle S\to AS~|~BS~|~C~|~\epsilon }
C → R C | L {\displaystyle C\to RC~|~L}
R → − f R A {\displaystyle R{\xrightarrow[{-f}]{}}RA}
R → − g R B {\displaystyle R{\xrightarrow[{-g}]{}}RB}
R → # ϵ {\displaystyle R{\xrightarrow[{\#}]{}}\epsilon }
A → + f a {\displaystyle A{\xrightarrow[{+f}]{}}a}
B → + g b {\displaystyle B{\xrightarrow[{+g}]{}}b}
L → − f L a | a {\displaystyle L{\xrightarrow[{-f}]{}}La~|~a}
L → − g L b | b {\displaystyle L{\xrightarrow[{-g}]{}}Lb~|~b}
A derivation for the string ababab is as follows:
… excerpt ends here. Continue reading the full article.
