| dbpprop:abstract
|
- In computer science, a context-free grammar is said to be in Chomsky normal form if all of its production rules are of the form: <math>A</math><math>\rightarrow\, </math><math>BC</math> or <math>A</math><math>\rightarrow\, </math>α or <math>S</math><math>\rightarrow\, </math>λ where <math>A</math>, <math>B</math> and <math>C</math> are nonterminal symbols, α is a terminal symbol (a symbol that represents a constant value), <math>S</math> is the start symbol, and λ is the empty string. Also, neither <math>B</math> nor <math>C</math> may be the start symbol. Every grammar in Chomsky normal form is context-free, and conversely, every context-free grammar can be efficiently transformed into an equivalent one which is in Chomsky normal form. With the exception of the optional rule <math>S</math><math> \rightarrow\, </math>λ (included when the grammar may generate the empty string), all rules of a grammar in Chomsky normal form are expansive; thus, throughout the derivation of a string, each string of terminals and nonterminals is always either the same length or one element longer than the previous such string. The derivation of a string of length n is always exactly <math>2n-1</math> steps long. Furthermore, since all rules deriving nonterminals transform one nonterminal to exactly two nonterminals, a parse tree based on a grammar in Chomsky normal form is a binary tree, and the height of this tree is limited to at most the length of the string. Because of these properties, many proofs in the field of languages and computability make use of the Chomsky normal form. These properties also yield various efficient algorithms based on grammars in Chomsky normal form; for example, the CYK algorithm that decides whether a given string can be generated by a given grammar uses the Chomsky normal form. The Chomsky normal form is named after Noam Chomsky, the US linguist who invented the Chomsky hierarchy.
- Die Chomsky-Normalform ist eine kontextfreie Grammatik mit einer besonders einfachen Struktur der Produktionen. Sie ist ein Begriff aus der Theorie der formalen Sprachen, einem Teilbereich der Theoretischen Informatik. Sie ist nach dem US-Linguisten Noam Chomsky benannt und kommt beim CYK-Algorithmus zum Einsatz. Zu jeder kontextfreien Sprache gibt es eine Chomsky-Normalform. Deshalb kann aus jeder kontextfreien Grammatik <math>G</math> eine Chomsky-Normalform <math>G_{CNF}</math> konstruiert werden, die dieselbe Sprache erzeugt. Die Grammatik <math>G_{CNF}</math> wird dann auch eine Chomsky-Normalform der kontextfreien Grammatik <math>G</math> genannt. Eine Erweiterung der Chomsky-Normalform auf kontextsensitive Grammatiken stellt die Kuroda-Normalform dar.
- Chomského normální forma je tvar formální gramatiky ve které jsou všechna odvozovací pravidla tvaru: A → BC nebo A → α nebo S → ε kde A, B a C jsou neterminály, α je terminál, S je startovní neterminál a ε je prázdný řetězec, přičemž B ani C nemohou být startovacím neterminálem. Každá gramatika v Chomského normální formě je bezkontextová a naopak, každou bezkontextovou gramatiku lze transformovat do Chomského normální formy. S výjimkou volitelného pravidla S → λ (které je povoleno pro případ, kdy má gramatika generovat prázdný řetězec) jsou všechna pravidla nezkracující, tzn. při každém odvození je každý řetězec stejně dlouhý nebo delší než předchozí (ve významu času) řetězec. Jelikož všechna pravidla odvozující neterminály transformují jeden neterminál na právě dva, je parsovacím stromem je binární strom a jeho výška je maximálně délka generovaného řetězce. Forma je pojmenována po svém autorovi, Noamovi Chomském. Chomského normální forma je často používána v CYK algoritmu.
- Una gramática formal está en Forma normal de Chomsky si todas sus reglas de producción tienen de una de las siguientes formas: <math>A</math><math>\rightarrow\, </math><math>BC</math> o <math>A</math><math>\rightarrow\, </math>α o <math>S</math><math>\rightarrow\, </math>λ donde <math>S</math> es el símbolo distinguido (o inicial) de la gramática, <math>A</math>, <math>B</math> y <math>C</math> son símbolos no terminales (o variables) distintos de <math>S</math>, α es un símbolo terminal, y λ es la cadena nula (o vacía).
- Tietojenkäsittelytieteessä formaali kielioppi on Chomskyn normaalimuodossa jos ja vain jos sen kaikki produktiot ovat muotoa A → BC A → α tai S → ε missä A, B ja C ovat välikkeitä, α on päätemerkki, S lähtösymboli ja ε tyhjä merkkijono. Kieliopin välikkeistä vain S saa olla tyhjentyvä eli tuottaa tyhjän merkkijonon.
- En informatique, une grammaire formelle est en forme normale de Chomsky si et seulement si toutes ses règles de production sont de la forme : A → BC ou A → α ou S → ε où A, B et C sont des symboles non-terminaux, α est un symbole terminal (représentant une valeur constante), S est l'axiome de la grammaire, et ε est le mot vide, tels que l'axiome n'apparaît jamais dans le membre droit d'une règle (autrement dit, ni B ni C ne peuvent être S). Toute grammaire écrite en forme normale de Chomsky est une grammaire hors-contexte. Inversement, toute grammaire hors-contexte peut être transformée en une grammaire équivalente en forme normale de Chomsky. À l'exception de la règle optionnelle S → ε (incluse si la grammaire peut générer le mot vide), toutes les règles d'une grammaire sous forme normale de Chomsky sont extensibles; par conséquent, tout au long de la suite de dérivations, chaque chaîne de terminaux et non-terminaux est toujours de la même longueur ou plus longue d'un élément seulement que la chaîne de l'étape précédente. La dérivation d'une chaîne de longueur n se fait donc toujours au plus en 2n-1 étapes. De plus, dans la mesure où toutes les règles de dérivation de non-terminaux transforment un non-terminal en deux non-terminaux, un arbre de dérivation basé sur une grammaire en forme normale de Chomsky est un arbre binaire, et sa hauteur est au maximum la longueur de la chaîne de caractères. Grâce à ces propriétés, de nombreuses preuves dans le domaine des langages formels utilisent la forme normale de Chomsky. Plusieurs algorithmes efficaces tirent également profit de ces propriétés, comme par exemple l'algorithme CYK, permettant de décider si une chaîne de caractères peut être générée par une grammaire mise en forme normale de Chomsky. La forme normale de Chomsky tient son nom du linguiste américain Noam Chomsky, également inventeur de la hiérarchie qui porte son nom.
- 計算機科学における形式文法で、次のような生成規則のみからなる文法をチョムスキー標準形（チョムスキーひょうじゅんけい）という。 <math> A \rightarrow BC </math> または <math> A \rightarrow \alpha</math> または <math> S \rightarrow \varepsilon </math> ここで、A 、 B および C は非終端記号、α は終端記号であり、Sは開始記号を表し、ε は空列を表すものとする。 また、チョムスキー標準形には次のような性質が挙げられる。 チョムスキー標準形で表すことのできる文法は全て文脈自由であり、また全ての文脈自由文法は、これと等価なチョムスキー標準形の文法に書き換えることができる。 S→ε型の規則（空列を導出する文法に含まれる）を除いて、チョムスキー標準形の文法における全ての生成規則は拡張的である。つまり、終端記号と非終端記号からなる文字列に生成規則を適用して生成される文字列の長さは元の文字列の長さよりも等しいか、あるいは長くなる。 長さ n の文字列を導出するには、2n-1 回以上規則を適用する必要がある。 1つの非終端記号から導出される非終端記号は常に2つとなり、構文木は二分木で表されるため、木の深さは最大でも文字列の長さである。 これらの性質から、言語理論や計算複雑性理論の分野における証明では、しばしばチョムスキー標準形が用いられる。また、CYKアルゴリズム（チョムスキー標準形の文法が与えられた文字列を生成できるか否かを決定するアルゴリズム）のように、様々な効率的なアルゴリズムの基礎となっている。 チョムスキー標準形の名前は、チョムスキー階層を発表した米国の言語学者ノーム・チョムスキーにちなんで名付けられたものである。
- Chomsky-normaalvorm is een begrip uit de theoretische informatica, in het bijzonder het gebied der formele talen. De Chomsky-normaalvorm is een kenmerk dat een formele grammatica al dan niet kan bezitten. De Chomsky-normaalvorm is interessant vanuit het oogpunt van berekenbaarheid; veel bewijzen maken er gebruik van. Daarbij leiden grammatica's in de Chomsky-normaalvorm tot efficiënte algoritmes; een voorbeeld is het CYK-algoritme, dat beslist of een gegeven string gegenereerd kan worden door een gegeven grammatica. De Chomsky-normaalvorm is genoemd naar Noam Chomsky, de Amerikaanse taalkundige die de Chomskyhiërarchie bedacht.
- Postać normalna Chomsky'ego to postać gramatyki bezkontekstowej, w której wszystkie reguły są postaci: <math>A \rightarrow a</math> <math>A \rightarrow BC</math> gdzie małe litery oznaczają symbole terminalne, duże zaś nieterminalne. Każdą gramatykę bezkontekstową niegenerującą symbolu pustego można przekształcić do postaci normalnej Chomsky'ego. Żeby rozszerzyć ten zbiór do wszystkich gramatyk bezkontekstowych, rozszerza się czasem postać normalną Chomsky'ego o reguły: <math>S \rightarrow \epsilon</math> (<math>S</math> – symbol startowy, <math>\epsilon</math> – słowo puste), ale gramatyka zawierająca taką regułkę nie może zawierać <math>S</math> po prawej stronie żadnej reguły. Gramatyka taka to de facto alternatywa gramatyki w postaci normalnej oraz gramatyki generującej tylko symbol pusty.
- В информатике говорят, что формальная грамматика находится в нормальной форме Хомского, если все ее продукции имеют вид <math>A</math><math>\rightarrow\, </math><math>BC</math> или <math>A</math><math>\rightarrow\, </math>α или <math>S</math><math>\rightarrow\, </math>ε где <math>A</math>, <math>B</math> и <math>C</math> — нетерминалы, α — терминальный символ (представляющий постоянное значение), <math>S</math> — начальный символ, и ε — пустая строка. Также ни <math>B</math>, ни <math>C</math> не может быть начальным символом. Каждая грамматика в нормальной форме Хомского является контекстно-свободной, и наоборот, каждая контекстно-свободная грамматика может быть эффективно преобразована в эквивалентную грамматику в нормальной форме Хомского. За исключением возможного правила <math>S</math><math> \rightarrow\, </math>ε (используемого, когда грамматика может порождать пустую строку), все правила грамматики в нормальной форме Хомского неукорачивающие; то есть, в процессе вывода строки каждая цепочка из терминалов и нетерминалов всегда имеет либо ту же длину, что и предыдущая, либо на один элемент больше. Вывод строки длины <math>n</math> всегда занимает ровно <math>2n-1</math> шагов. Кроме того, так как все правила вывода нетерминалов переводят один нетерминал в ровно два нетерминала, дерево разбора, основанное на грамматике в нормальной форме Хомского, составляет собой бинарное дерево, высота которого ограничена длиной строки. Благодаря этим свойствам, многие доказательства в теории формальных языков и вычислимости используют нормальную форму Хомского. Эти свойства также служат основой различных эффективных алгоритмов — например, CYK-алгоритм, определяющий, может ли данная строка порождаться данной грамматикой, использует нормальную форму Хомского. Нормальная форма Хомского названа по имени Ноама Хомского, американского лингвиста, предложившего иерархию Хомского.
- 在计算机科学中，一个形式文法是 Chomsky 范式的，当且仅当所有产生规则都有如下形式： A → BC 或 A → α 或 S → ε 这里的 A, B 和 C 是非终结符，α 是终结符（表示常量值的符号），S 是开始符号，而 ε 是空串。还有，B 和 C 都不可以是开始符号。 所有的 Chomsky 范式的文法都是上下文无关，反过来，所有上下文无关文法都可以有效的变换成等价的 Chomsky 范式的文法。 除了（在文法可能生成空串的时候包括的）可选规则 S → ε 是例外，Chomsky 范式的文法的所有规则都是扩张的，就是说在字符串的整个导出过程中，每个终结符和非终结符的字符串比起前面导出的字符串要么同样长度要么多出一个元素。长度 n 的字符串的导出总是精确的 2n-1 步长。进一步的，因为导出非终结符的所有规则都把一个非终结符变换成两个非终结符，基于 Chomsky 范式的文法上的一个分析树是二叉树，而这个树的高度被限制于最高为这个字符串的长度。 由于这些性质，在语言和可计算性领域中很多证明采用了 Chomsky 范式。这些性质还产生了基于 Chomsky 范式的文法的各种有效算法；例如，判定给定字符串是否可以被使用 Chomsky 范式的给定文法生成的 CYK算法。 Chomsky 范式得名于诺姆·乔姆斯基，他是发明乔姆斯基层级的美国语言学家。
|
| rdfs:comment
|
- Die Chomsky-Normalform ist eine kontextfreie Grammatik mit einer besonders einfachen Struktur der Produktionen. Sie ist ein Begriff aus der Theorie der formalen Sprachen, einem Teilbereich der Theoretischen Informatik. Sie ist nach dem US-Linguisten Noam Chomsky benannt und kommt beim CYK-Algorithmus zum Einsatz. Zu jeder kontextfreien Sprache gibt es eine Chomsky-Normalform.
- Chomského normální forma je tvar formální gramatiky ve které jsou všechna odvozovací pravidla tvaru: A → BC nebo A → α nebo S → ε kde A, B a C jsou neterminály, α je terminál, S je startovní neterminál a ε je prázdný řetězec, přičemž B ani C nemohou být startovacím neterminálem. Každá gramatika v Chomského normální formě je bezkontextová a naopak, každou bezkontextovou gramatiku lze transformovat do Chomského normální formy.
- Tietojenkäsittelytieteessä formaali kielioppi on Chomskyn normaalimuodossa jos ja vain jos sen kaikki produktiot ovat muotoa A → BC A → α tai S → ε missä A, B ja C ovat välikkeitä, α on päätemerkki, S lähtösymboli ja ε tyhjä merkkijono. Kieliopin välikkeistä vain S saa olla tyhjentyvä eli tuottaa tyhjän merkkijonon.
- En informatique, une grammaire formelle est en forme normale de Chomsky si et seulement si toutes ses règles de production sont de la forme : A → BC ou A → α ou S → ε où A, B et C sont des symboles non-terminaux, α est un symbole terminal (représentant une valeur constante), S est l'axiome de la grammaire, et ε est le mot vide, tels que l'axiome n'apparaît jamais dans le membre droit d'une règle (autrement dit, ni B ni C ne peuvent être S).
- Chomsky-normaalvorm is een begrip uit de theoretische informatica, in het bijzonder het gebied der formele talen. De Chomsky-normaalvorm is een kenmerk dat een formele grammatica al dan niet kan bezitten. De Chomsky-normaalvorm is interessant vanuit het oogpunt van berekenbaarheid; veel bewijzen maken er gebruik van.
- Postać normalna Chomsky'ego to postać gramatyki bezkontekstowej, w której wszystkie reguły są postaci: <math>A \rightarrow a</math> <math>A \rightarrow BC</math> gdzie małe litery oznaczają symbole terminalne, duże zaś nieterminalne. Każdą gramatykę bezkontekstową niegenerującą symbolu pustego można przekształcić do postaci normalnej Chomsky'ego.
|
![[RDF Data]](/statics/sw-cube.png)
