An indexed grammar is a formal grammar which describes indexed languages. They have three disjoint sets of symbols: the usual terminals and nonterminals and the indices, which appear only in intermediate derivation steps. Productions can replace a nonterminal with a string of terminals and nonterminals like in context-free grammars, but also a nonterminal with a nonterminal followed by an index and a nonterminal followed by an index with a nonterminal.

PropertyValue
dbpprop:abstract
  • An indexed grammar is a formal grammar which describes indexed languages. They have three disjoint sets of symbols: the usual terminals and nonterminals and the indices, which appear only in intermediate derivation steps. Productions can replace a nonterminal with a string of terminals and nonterminals like in context-free grammars, but also a nonterminal with a nonterminal followed by an index and a nonterminal followed by an index with a nonterminal. Indices can appear only after a nonterminal or after another index, so every nonterminal can be considered the "owner" of the indices that follow it, which form a stack (indices are added or removed by productions right after the nonterminal). In practice, stacks of indices can count and remember what rules were applied and in which order. For example, indexed grammars can describe this non context-free language: <math> L = \{a^n b^n c^n | n \geq 1 \} </math> with these rules (f and g are indices): <math>S\to aAfc</math> <math>A\to aAgc ~|~ B</math> <math>Bf\to b</math> <math>Bg\to bB</math> The stack of g's that grows in the middle counts how many times (<math>n-1</math>) A has been expanded to add one a and one c; every g becomes a terminal b at the end. The problem of determining whether a string is recognized by an indexed grammar is NP-complete.
  • 附标文法是描述附标语言的形式文法。它们有三个无交集的符号集合: 普通终结符、非终结符和只出现在中间推导中的附标(index)的集合。产生式可以如上下文无关文法那样把一个非终结符替代为终结符和非终结符的字符串，但是它还把非终结符替代为跟随着一个附标的非终结符，把跟随着一个附标的非终结符替代为非终结符。 附标只可以出现在非终结符之后或其他附标之后，所以所有非终结符都可以被看作跟随它之后的这些附标的所有者，它们形成了一个栈(产生式在非终结符之后增加或去除附标)。 实际上，附标的栈可以计数并记住应用了和以何种次序应用了什么规则。例如，附标文法可以描述非上下无关语言: <math> L = \{a^n b^n c^n | n \geq 1 \} </math> 通过如下规则(f 和 g 是附标): <math>S\to aAfc</math> <math>A\to aAgc ~|~ B</math> <math>Bf\to b</math> <math>Bg\to bB</math> 在中间增长的 g 的栈计数 A 已经被展开来增加一个 a 和一个 c 的次数 (<math>n-1</math>)；在结束时所有 g 变成终结符 b。 判定一个附标文法是否识别一个字符串是NP-完全的。
dbpprop:hasPhotoCollection
dbpprop:reference
rdf:type
rdfs:comment
  • An indexed grammar is a formal grammar which describes indexed languages. They have three disjoint sets of symbols: the usual terminals and nonterminals and the indices, which appear only in intermediate derivation steps. Productions can replace a nonterminal with a string of terminals and nonterminals like in context-free grammars, but also a nonterminal with a nonterminal followed by an index and a nonterminal followed by an index with a nonterminal.
rdfs:label
  • Indexed grammar
  • 附标文法
owl:sameAs
skos:subject
foaf:page
is dbpprop:redirect of
is owl:sameAs of