In formal language theory, a grammar is in Kuroda normal form iff all production rules are of the form: AB → CD or A → BC or A → B or A → α where A, B, C and D are nonterminal symbols and α is a terminal symbol. Every grammar in Kuroda normal form is monotonic, and therefore, generates a context-sensitive language. Conversely, every context-sensitive language which does not generate the empty string can be generated by a grammar in Kuroda normal form.

PropertyValue
dbpprop:abstract
  • In formal language theory, a grammar is in Kuroda normal form iff all production rules are of the form: AB → CD or A → BC or A → B or A → α where A, B, C and D are nonterminal symbols and α is a terminal symbol. Every grammar in Kuroda normal form is monotonic, and therefore, generates a context-sensitive language. Conversely, every context-sensitive language which does not generate the empty string can be generated by a grammar in Kuroda normal form. It is named for linguist S. -Y. Kuroda.
  • Die Kuroda-Normalform ist ein Begriff der Theoretischen Informatik, der im Zusammenhang mit kontextsensitiven Sprachen von Interesse ist. Sie ist nach dem Linguisten S. -Y. Kuroda benannt und beschreibt eine Normalform der kontextsensitiven Grammatiken, also eine Teilmenge der kontextsensitiven Grammatiken, die gegenüber der Menge der allgemeinen kontextsensitiven Grammatiken nichts an Ausdrucksstärke einbüßt. Die Bedeutung der Kuroda-Normalform liegt in der sehr einfachen Struktur der Produktionen. Die Kuroda-Normalform ist eine Verallgemeinerung der Chomsky-Normalform, die ebenfalls eine Normalform für kontextsensitive Grammatiken darstellt, deren Einschränkung auf kontextfreie Grammatiken eine große Bedeutung erlangt hat.
  • In informatica, una grammatica formale è espressa in in forma normale di Kuroda se tutte le sue produzioni sono della forma: AB → CD oppure A → BC oppure A → B oppure A → α dove A, B, C e D sono simboli non terminali α è un simbolo terminale. Ogni grammatica in forma normale di Kuroda genera un Linguaggio sensibile al contesto, e, viceversa, ogni linguaggio sensibile al contesto che non produce la stringa vuota può essere generata da una grammatica in forma normale di Kuroda.
  • 形式言語理論において、ある形式文法の全ての生成規則が次のいずれかの形式をもつとき、その文法は黒田標準形（くろだひょうじゅんけい Kuroda normal form）であるという： AB → CD A → BC A → B A → α ここで A, B, C, D は非終端記号であり α は終端記号である。 黒田標準形をもつ文法によって生成される言語は全て文脈依存言語である。逆に、空文字列を含まない文脈依存言語は全て黒田標準形をもつ文法によって生成することができる。 言語学者黒田成幸の研究に基づく。
  • Gramatyka formalna jest w postaci normalnej Kurody, jeśli zawiera tylko produkcje postaci: <math>AB \rightarrow CD</math>, <math>A \rightarrow BC</math>, <math>A \rightarrow B</math>, <math>A \rightarrow \alpha</math>, gdzie A,B i C to symbole nieterminalne, a <math>\alpha</math> - symbol terminalny. Każda gramatyka w postaci normalnej Kurody generuje język kontekstowy, jak również dla każdej gramatyki kontekstowej nie generującej słowa pustego istnieje równoważna jej gramatyka w postaci normalnej Kurody.
  • 在计算机科学中，形式文法是 Kuroda 范式的，当且仅当所有产生规则都有如下形式: AB → CD 或 A → BC 或 A → B 或 A → α 这里的 A, B, C 和 D 是非终结符而 α 是终结符。 所有 Kuroda 范式的文法都是单调的，因此生成上下文有关语言。反过来说，所有不生成空串的上下文有关语言都可以被 Kuroda 范式的文法所生成。
dbpprop:hasPhotoCollection
rdf:type
rdfs:comment
  • In formal language theory, a grammar is in Kuroda normal form iff all production rules are of the form: AB → CD or A → BC or A → B or A → α where A, B, C and D are nonterminal symbols and α is a terminal symbol. Every grammar in Kuroda normal form is monotonic, and therefore, generates a context-sensitive language. Conversely, every context-sensitive language which does not generate the empty string can be generated by a grammar in Kuroda normal form.
  • Die Kuroda-Normalform ist ein Begriff der Theoretischen Informatik, der im Zusammenhang mit kontextsensitiven Sprachen von Interesse ist. Sie ist nach dem Linguisten S. -Y. Kuroda benannt und beschreibt eine Normalform der kontextsensitiven Grammatiken, also eine Teilmenge der kontextsensitiven Grammatiken, die gegenüber der Menge der allgemeinen kontextsensitiven Grammatiken nichts an Ausdrucksstärke einbüßt.
  • In informatica, una grammatica formale è espressa in in forma normale di Kuroda se tutte le sue produzioni sono della forma: AB → CD oppure A → BC oppure A → B oppure A → α dove A, B, C e D sono simboli non terminali α è un simbolo terminale.
  • Gramatyka formalna jest w postaci normalnej Kurody, jeśli zawiera tylko produkcje postaci: <math>AB \rightarrow CD</math>, <math>A \rightarrow BC</math>, <math>A \rightarrow B</math>, <math>A \rightarrow \alpha</math>, gdzie A,B i C to symbole nieterminalne, a <math>\alpha</math> - symbol terminalny.
  • 在计算机科学中，形式文法是 Kuroda 范式的，当且仅当所有产生规则都有如下形式: AB → CD 或 A → BC 或 A → B 或 A → α 这里的 A, B, C 和 D 是非终结符而 α 是终结符。 所有 Kuroda 范式的文法都是单调的，因此生成上下文有关语言。反过来说，所有不生成空串的上下文有关语言都可以被 Kuroda 范式的文法所生成。
rdfs:label
  • Kuroda normal form
  • Kuroda-Normalform
  • Forma normale di Kuroda
  • 黒田標準形
  • Postać normalna Kurody
  • 黑田范式
owl:sameAs
skos:subject
foaf:page
is owl:sameAs of