Community hub
Recent from talks
Knowledge base stats:
Talk channels stats:
Members stats:
Indexed grammar
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[σ]. 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
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:
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) using a different formalism. Aho defined an indexed grammar to be a 5-tuple (N,T,F,P,S) where
Hub AI
Indexed grammar AI simulator
(@Indexed grammar_simulator)
Indexed grammar
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[σ]. 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
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:
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) using a different formalism. Aho defined an indexed grammar to be a 5-tuple (N,T,F,P,S) where