Chomsky normal form
http://dbpedia.org/resource/Chomsky_normal_form an entity of type: Thing
Una gramática formal está en Forma normal de Chomsky si todas sus reglas de producción son de alguna de las siguientes formas: oα donde , y son símbolos no terminales (o variables) y α es un símbolo terminal. Todo que no posee a la cadena vacía, es expresable por medio de una gramática en forma normal de Chomsky (GFNCH) y recíprocamente. Además, dada una gramática independiente del contexto, es posible algorítmicamente producir una GFNCH equivalente, es decir, que genera el mismo lenguaje.
rdf:langString
En informatique théorique, et notamment en théorie des langages, une grammaire non contextuelle est en forme normale de Chomsky si et seulement si toutes ses règles de production sont de la forme : 1.
* ; 2.
* ou ; 3.
* ou où sont des symboles non terminaux, est un symbole terminal, est l'axiome de la grammaire, et est le mot vide. Si la dernière règle est présente, il est demandé que l'axiome n'apparaisse jamais dans le membre droit d'une règle.
rdf:langString
在计算机科学中，一个形式文法是 Chomsky 范式的，当且仅当所有产生规则都有如下形式： A → BC 或A → α 或S → ε 这里的 A, B 和 C 是非终结符，α 是终结符（表示常量值的符号），S 是开始符号，而 ε 是空串。还有，B 和 C 都不可以是开始符号。 所有的 Chomsky 范式的文法都是上下文无关，反过来，所有上下文无关文法都可以有效的变换成等价的 Chomsky 范式的文法。 除了（在文法可能生成空串的时候包括的）可选规则 S → ε 是例外，Chomsky 范式的文法的所有规则都是扩张的，就是说在字符串的整个导出过程中，每个终结符和非终结符的字符串比起前面导出的字符串要么同样长度要么多出一个元素。长度 n 的字符串的导出总是精确的 2n-1 步长。 Chomsky 范式得名于诺姆·乔姆斯基，他是发明乔姆斯基层级的美国语言学家。
rdf:langString
Нормальна форма Чомскі або нормальна форма Хомського (НФХ - бінарна нормальна форма) встановлюється для приведеної контекстно-вільної (КС) граматики, всі правила якої мають вигляд: 1. A->BC, де A,B,C належать N (множині нетермінальних символів), ані B ані C не можуть бути джерелом S.2. A-> a, де a належить 3. S -> , якщо L(G), де S - джерело.
rdf:langString
صيغة تشومسكي العادية تسمى اللغة الخالية من السياق في علوم الحاسب الآلي بأنها صيغة تشومسكي العادية (Chomsky normal form)، إذا كانت كافة قواعد إنتاجها على الصيغة: أو أو حيث , و رموزا تمثل قيمة متغيرة، بينما رمزا α يمثل قيمة ثابتة، و S رمز بداية، و ε حقل فارغ. كما أن B أو C لا يمكن أن يمثلا رمز بداية. كل لغة بصيغة تشومسكي العادية خالية من السياق، وبالعكس يمكن تحويل كل لغة خالية من السياق إلى لغة بصيغة تشومسكي العادية. وهناك عدة لوغريتمات معروفة للقيام بمثل هذا التحويل. وتوصف التحويلات في أغلب الكتب الدراسية المتخصصة في نظرية الأتمتة، ومنها كتاب هوبكروفت وأولمان (Hopcroft and Ullman, 1979). وكما بيّن لانغ ولايس، فإن العيب في هذه التحويلات هو أنها قد تؤدي إلى مط غير مرغوب في حجم اللغة. وباستخدام | G | للرمز إلى حجم اللغة الأصلية G، فإن حجم المط في أسوأ الحالات قد يتراوح ما بين | G | 2 إلى 22
rdf:langString
En informàtica, una gramàtica lliure de context G es diu que està en la forma normal de Chomsky si totes les seves regles són de la forma: on és qualsevol símbol terminal (un símbol que representa un valor constant) i A, B i C són símbols no terminals, B i C no poden ser el símbol inicial. També es permet la regla: on S és la variable inicial i la paraula buida (també pot estar representada per λ), aquesta última regla només pot aparèixer si és a L(G), és a dir, el llenguatge produït per la gramàtica lliure del context G.
rdf:langString
Chomského normální forma je tvar formální gramatiky ve které jsou všechna odvozovací pravidla tvaru: A → BC neboA → α neboS → ε (je povoleno pokud gramatika generuje prázdný řetězec a zároveň se S nevyskytuje na pravé straně žádného pravidla) 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. Forma je pojmenována po svém autorovi, Noamovi Chomském.
rdf:langString
In formal language theory, a context-free grammar, G, is said to be in Chomsky normal form (first described by Noam Chomsky) if all of its production rules are of the form: A → BC, orA → a, orS → ε, where A, B, and C are nonterminal symbols, the letter a is a terminal symbol (a symbol that represents a constant value), S is the start symbol, and ε denotes the empty string. Also, neither B nor C may be the start symbol, and the third production rule can only appear if ε is in L(G), the language produced by the context-free grammar G.
rdf:langString
Die Chomsky-Normalform (Abk.: CNF) ist in der theoretischen Informatik eine Normalform für kontextfreie Grammatiken. Sie ist nach dem Linguisten Noam Chomsky benannt und kommt beim CYK-Algorithmus zum Einsatz. Eine kontextfreie Grammatik in Chomsky-Normalform hat eine einfache Struktur der Produktionsregeln und erfüllt auch die Eigenschaften kontextsensitiver Grammatiken.
rdf:langString
Nella teoria dei linguaggi formali, una grammatica libera dal contesto si dice essere nella forma normale di Chomsky (CNF, o FNC, dall'inglese Chomsky normal form) (scoperta da Noam Chomsky) se tutte le sue regole di produzione sono nella forma seguente: o o, dove , e sono simboli non terminali, è un simbolo terminale (un simbolo che rappresenta un valore costante), è l'assioma di partenza, è la stringa vuota, e .
rdf:langString
言語の理論（形式言語の理論）において、次のような生成規則のみからなる文法をチョムスキー標準形（チョムスキーひょうじゅんけい）という。 または または ここで、A 、 B および C は非終端記号、α は終端記号であり、Sは開始記号を表し、ε は空列を表すものとする。 また、チョムスキー標準形には次のような性質が挙げられる。
* チョムスキー標準形で表すことのできる文法は全て文脈自由であり、また全ての文脈自由文法は、これと等価なチョムスキー標準形の文法に書き換えることができる。
* S→ε型の規則（空列を導出する文法に含まれる）を除いて、チョムスキー標準形の文法における全ての生成規則は拡張的である。つまり、終端記号と非終端記号からなる文字列に生成規則を適用して生成される文字列の長さは元の文字列の長さよりも等しいか、あるいは長くなる。
* 長さ n の文字列を導出するには、2n-1 回以上規則を適用する必要がある。
* 1つの非終端記号から導出される非終端記号は常に2つとなり、構文木は二分木で表されるため、木の深さは最大でも文字列の長さである。 チョムスキー標準形の名前はノーム・チョムスキーにちなむ。
rdf:langString
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.
rdf:langString
Postać normalna Chomsky’ego to postać gramatyki bezkontekstowej, w której wszystkie reguły (inaczej: produkcje) są postaci: 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: ( – symbol startowy, – słowo puste), ale gramatyka zawierająca taką regułkę nie może zawierać po prawej stronie żadnej reguły.
rdf:langString
Em ciência da computação, uma gramática livre de contexto está na forma normal de Chomsky se todas as suas regras de produção são da forma: ou ou onde , e são variáveis (símbolos não-terminais), α é um símbolo terminal (um símbolo que representa um valor constante), é a variável inicial, e ε é a cadeia vazia. Além disso, nem nem podem ser a variável inicial.
rdf:langString
Нормальная форма Хомского — свойство формальной грамматики, если все её продукции имеют вид: или или, где , и — нетерминалы, — терминальный символ (представляющий постоянное значение), — начальный символ, и — пустая строка. Также ни , ни не может быть начальным символом. Каждая грамматика в нормальной форме Хомского является контекстно-свободной, и наоборот, каждая контекстно-свободная грамматика может быть эффективно преобразована в эквивалентную грамматику в нормальной форме Хомского. Названа по имени Ноама Хомского, американского лингвиста, предложившего иерархию Хомского.
rdf:langString
rdf:langString
نموذج تشومسكي الطبيعي
rdf:langString
Forma normal de Chomsky
rdf:langString
Chomského normální forma
rdf:langString
Chomsky-Normalform
rdf:langString
Chomsky normal form
rdf:langString
Forma normal de Chomsky
rdf:langString
Forma normale di Chomsky
rdf:langString
Forme normale de Chomsky
rdf:langString
チョムスキー標準形
rdf:langString
Chomsky-normaalvorm
rdf:langString
Postać normalna Chomsky’ego
rdf:langString
Forma Normal de Chomsky
rdf:langString
Нормальная форма Хомского
rdf:langString
乔姆斯基范式
rdf:langString
Нормальна форма Чомскі
xsd:integer
7850
xsd:integer
1096562422
rdf:langString
En informàtica, una gramàtica lliure de context G es diu que està en la forma normal de Chomsky si totes les seves regles són de la forma: on és qualsevol símbol terminal (un símbol que representa un valor constant) i A, B i C són símbols no terminals, B i C no poden ser el símbol inicial. També es permet la regla: on S és la variable inicial i la paraula buida (també pot estar representada per λ), aquesta última regla només pot aparèixer si és a L(G), és a dir, el llenguatge produït per la gramàtica lliure del context G. Tota gramàtica en forma normal de Chomsky és lliure del context, i per contra, tota gramàtica lliure del context es pot transformar en una equivalent en forma normal de Chomsky i té una mida menor al quadrat de la mida de la gramàtica original.
rdf:langString
Chomského normální forma je tvar formální gramatiky ve které jsou všechna odvozovací pravidla tvaru: A → BC neboA → α neboS → ε (je povoleno pokud gramatika generuje prázdný řetězec a zároveň se S nevyskytuje na pravé straně žádného pravidla) 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 → ɛ 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 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.
rdf:langString
صيغة تشومسكي العادية تسمى اللغة الخالية من السياق في علوم الحاسب الآلي بأنها صيغة تشومسكي العادية (Chomsky normal form)، إذا كانت كافة قواعد إنتاجها على الصيغة: أو أو حيث , و رموزا تمثل قيمة متغيرة، بينما رمزا α يمثل قيمة ثابتة، و S رمز بداية، و ε حقل فارغ. كما أن B أو C لا يمكن أن يمثلا رمز بداية. كل لغة بصيغة تشومسكي العادية خالية من السياق، وبالعكس يمكن تحويل كل لغة خالية من السياق إلى لغة بصيغة تشومسكي العادية. وهناك عدة لوغريتمات معروفة للقيام بمثل هذا التحويل. وتوصف التحويلات في أغلب الكتب الدراسية المتخصصة في نظرية الأتمتة، ومنها كتاب هوبكروفت وأولمان (Hopcroft and Ullman, 1979). وكما بيّن لانغ ولايس، فإن العيب في هذه التحويلات هو أنها قد تؤدي إلى مط غير مرغوب في حجم اللغة. وباستخدام | G | للرمز إلى حجم اللغة الأصلية G، فإن حجم المط في أسوأ الحالات قد يتراوح ما بين | G | 2 إلى 22 | G | ، تبعاً للتحول في اللوغاريتم المستخدم (Lange and Leiß, 2009).
rdf:langString
Die Chomsky-Normalform (Abk.: CNF) ist in der theoretischen Informatik eine Normalform für kontextfreie Grammatiken. Sie ist nach dem Linguisten Noam Chomsky benannt und kommt beim CYK-Algorithmus zum Einsatz. Eine kontextfreie Grammatik in Chomsky-Normalform hat eine einfache Struktur der Produktionsregeln und erfüllt auch die Eigenschaften kontextsensitiver Grammatiken. Zu jeder kontextfreien Sprache gibt es eine Grammatik in Chomsky-Normalform. Aus jeder kontextfreien Grammatik kann eine Grammatik in Chomsky-Normalform konstruiert werden, die dieselbe Sprache erzeugt. Die Grammatik wird dann auch eine Chomsky-Normalform der kontextfreien Grammatik genannt. Eine weitere Normalform für kontextfreie Grammatiken ist die Greibach-Normalform.Eine Erweiterung der Chomsky-Normalform auf kontextsensitive Grammatiken stellt die Kuroda-Normalform dar.Die Chomsky-Normalform wird auf Grund der gleichen Abkürzung leicht mit der Konjunktiven Normalform (engl. conjunctive normal form) verwechselt.
rdf:langString
In formal language theory, a context-free grammar, G, is said to be in Chomsky normal form (first described by Noam Chomsky) if all of its production rules are of the form: A → BC, orA → a, orS → ε, where A, B, and C are nonterminal symbols, the letter a is a terminal symbol (a symbol that represents a constant value), S is the start symbol, and ε denotes the empty string. Also, neither B nor C may be the start symbol, and the third production rule can only appear if ε is in L(G), the language produced by the context-free grammar G. Every grammar in Chomsky normal form is context-free, and conversely, every context-free grammar can be transformed into an equivalent one which is in Chomsky normal form and has a size no larger than the square of the original grammar's size.
rdf:langString
Una gramática formal está en Forma normal de Chomsky si todas sus reglas de producción son de alguna de las siguientes formas: oα donde , y son símbolos no terminales (o variables) y α es un símbolo terminal. Todo que no posee a la cadena vacía, es expresable por medio de una gramática en forma normal de Chomsky (GFNCH) y recíprocamente. Además, dada una gramática independiente del contexto, es posible algorítmicamente producir una GFNCH equivalente, es decir, que genera el mismo lenguaje.
rdf:langString
En informatique théorique, et notamment en théorie des langages, une grammaire non contextuelle est en forme normale de Chomsky si et seulement si toutes ses règles de production sont de la forme : 1.
* ; 2.
* ou ; 3.
* ou où sont des symboles non terminaux, est un symbole terminal, est l'axiome de la grammaire, et est le mot vide. Si la dernière règle est présente, il est demandé que l'axiome n'apparaisse jamais dans le membre droit d'une règle.
rdf:langString
言語の理論（形式言語の理論）において、次のような生成規則のみからなる文法をチョムスキー標準形（チョムスキーひょうじゅんけい）という。 または または ここで、A 、 B および C は非終端記号、α は終端記号であり、Sは開始記号を表し、ε は空列を表すものとする。 また、チョムスキー標準形には次のような性質が挙げられる。
* チョムスキー標準形で表すことのできる文法は全て文脈自由であり、また全ての文脈自由文法は、これと等価なチョムスキー標準形の文法に書き換えることができる。
* S→ε型の規則（空列を導出する文法に含まれる）を除いて、チョムスキー標準形の文法における全ての生成規則は拡張的である。つまり、終端記号と非終端記号からなる文字列に生成規則を適用して生成される文字列の長さは元の文字列の長さよりも等しいか、あるいは長くなる。
* 長さ n の文字列を導出するには、2n-1 回以上規則を適用する必要がある。
* 1つの非終端記号から導出される非終端記号は常に2つとなり、構文木は二分木で表されるため、木の深さは最大でも文字列の長さである。 これらの性質から、や計算複雑性理論の分野における証明では、しばしばチョムスキー標準形が用いられる。また、CYKアルゴリズム（チョムスキー標準形の文法が与えられた文字列を生成できるか否かを決定するアルゴリズム）のように、様々な効率的なアルゴリズムの基礎となっている。 チョムスキー標準形の名前はノーム・チョムスキーにちなむ。
rdf:langString
Postać normalna Chomsky’ego to postać gramatyki bezkontekstowej, w której wszystkie reguły (inaczej: produkcje) są postaci: 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: ( – symbol startowy, – słowo puste), ale gramatyka zawierająca taką regułkę nie może zawierać po prawej stronie żadnej reguły. Gramatyka taka to de facto gramatyki w postaci normalnej oraz gramatyki generującej tylko symbol pusty.
rdf:langString
Nella teoria dei linguaggi formali, una grammatica libera dal contesto si dice essere nella forma normale di Chomsky (CNF, o FNC, dall'inglese Chomsky normal form) (scoperta da Noam Chomsky) se tutte le sue regole di produzione sono nella forma seguente: o o, dove , e sono simboli non terminali, è un simbolo terminale (un simbolo che rappresenta un valore costante), è l'assioma di partenza, è la stringa vuota, e . Tutte le grammatiche nella forma normale di Chomsky sono non contestuali e, viceversa, tutte le grammatiche non contestuali possono essere trasformate in grammatiche equivalenti in FNC. Per eseguire tale trasformazione sono stati ideati più algoritmi. Tuttavia, come fatto notare da Lange e Leiß, lo svantaggio di queste trasformazioni sta nel grande aumento della dimensione della grammatica, dove tale dimensione equivale alla somma delle dimensioni delle regole di produzione, le quali, a loro volta, equivalgono a 1 più la lunghezza della parte destra. Denotando con la dimensione della grammatica originale , la crescita di tale dimensione nel peggiore dei casi è compresa fra a (dipende dall'algoritmo di trasformazione utilizzato).
rdf:langString
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.
rdf:langString
Нормальная форма Хомского — свойство формальной грамматики, если все её продукции имеют вид: или или, где , и — нетерминалы, — терминальный символ (представляющий постоянное значение), — начальный символ, и — пустая строка. Также ни , ни не может быть начальным символом. Каждая грамматика в нормальной форме Хомского является контекстно-свободной, и наоборот, каждая контекстно-свободная грамматика может быть эффективно преобразована в эквивалентную грамматику в нормальной форме Хомского. За исключением возможного правила (используемого, когда грамматика может порождать пустую строку), все правила грамматики в нормальной форме Хомского неукорачивающие; то есть, в процессе вывода строки каждая цепочка из терминалов и нетерминалов всегда имеет либо ту же длину, что и предыдущая, либо на один элемент больше. Вывод строки длины всегда занимает ровно шагов. Кроме того, так как все правила вывода нетерминалов переводят один нетерминал в ровно один терминал или в ровно два нетерминала, , основанное на грамматике в нормальной форме Хомского, составляет собой бинарное дерево, высота которого ограничена длиной строки. Благодаря этим свойствам, многие доказательства в теории формальных языков и вычислимости используют нормальную форму Хомского. Эти свойства также служат основой различных эффективных алгоритмов — например, CYK-алгоритм, определяющий, может ли данная строка порождаться данной грамматикой, использует нормальную форму Хомского. Названа по имени Ноама Хомского, американского лингвиста, предложившего иерархию Хомского.
rdf:langString
Em ciência da computação, uma gramática livre de contexto está na forma normal de Chomsky se todas as suas regras de produção são da forma: ou ou onde , e são variáveis (símbolos não-terminais), α é um símbolo terminal (um símbolo que representa um valor constante), é a variável inicial, e ε é a cadeia vazia. Além disso, nem nem podem ser a variável inicial. Toda gramática na forma normal de Chomsky é uma livre de contexto, e inversamente, toda gramática livre de contexto pode ser transformada em uma equivalente que está na forma normal de Chomsky. Vários algoritmos para realizar tal transformação são conhecidos. Transformações são descritas na maioria dos livros sobre teoria dos autômatos, tais como (Hopcroft and Ullman, 1979).Como apontado por Lange and Leiß, a desvantagem destas transformações é que elas podem levar a um inchaço indesejável no tamanho da gramática. Usando para denotar o tamanho da gramática original , o tamanho do inchaço no pior dos casos pode variar de a , dependendo do algoritmo de transformação utilizado (Lange and Leiß, 2009).
rdf:langString
在计算机科学中，一个形式文法是 Chomsky 范式的，当且仅当所有产生规则都有如下形式： A → BC 或A → α 或S → ε 这里的 A, B 和 C 是非终结符，α 是终结符（表示常量值的符号），S 是开始符号，而 ε 是空串。还有，B 和 C 都不可以是开始符号。 所有的 Chomsky 范式的文法都是上下文无关，反过来，所有上下文无关文法都可以有效的变换成等价的 Chomsky 范式的文法。 除了（在文法可能生成空串的时候包括的）可选规则 S → ε 是例外，Chomsky 范式的文法的所有规则都是扩张的，就是说在字符串的整个导出过程中，每个终结符和非终结符的字符串比起前面导出的字符串要么同样长度要么多出一个元素。长度 n 的字符串的导出总是精确的 2n-1 步长。 Chomsky 范式得名于诺姆·乔姆斯基，他是发明乔姆斯基层级的美国语言学家。
rdf:langString
Нормальна форма Чомскі або нормальна форма Хомського (НФХ - бінарна нормальна форма) встановлюється для приведеної контекстно-вільної (КС) граматики, всі правила якої мають вигляд: 1. A->BC, де A,B,C належать N (множині нетермінальних символів), ані B ані C не можуть бути джерелом S.2. A-> a, де a належить 3. S -> , якщо L(G), де S - джерело.
xsd:nonNegativeInteger
19976
