| rdfs:comment
| - 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. (es)
- 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. (fr)
- 在计算机科学中，一个形式文法是 Chomsky 范式的，当且仅当所有产生规则都有如下形式： A → BC 或A → α 或S → ε 这里的 A, B 和 C 是非终结符，α 是终结符（表示常量值的符号），S 是开始符号，而 ε 是空串。还有，B 和 C 都不可以是开始符号。 所有的 Chomsky 范式的文法都是上下文无关，反过来，所有上下文无关文法都可以有效的变换成等价的 Chomsky 范式的文法。 除了（在文法可能生成空串的时候包括的）可选规则 S → ε 是例外，Chomsky 范式的文法的所有规则都是扩张的，就是说在字符串的整个导出过程中，每个终结符和非终结符的字符串比起前面导出的字符串要么同样长度要么多出一个元素。长度 n 的字符串的导出总是精确的 2n-1 步长。 Chomsky 范式得名于诺姆·乔姆斯基，他是发明乔姆斯基层级的美国语言学家。 (zh)
- Нормальна форма Чомскі або нормальна форма Хомського (НФХ - бінарна нормальна форма) встановлюється для приведеної контекстно-вільної (КС) граматики, всі правила якої мають вигляд: 1. A->BC, де A,B,C належать N (множині нетермінальних символів), ані B ані C не можуть бути джерелом S.2. A-> a, де a належить 3. S -> , якщо L(G), де S - джерело. (uk)
- صيغة تشومسكي العادية تسمى اللغة الخالية من السياق في علوم الحاسب الآلي بأنها صيغة تشومسكي العادية (Chomsky normal form)، إذا كانت كافة قواعد إنتاجها على الصيغة: أو أو حيث , و رموزا تمثل قيمة متغيرة، بينما رمزا α يمثل قيمة ثابتة، و S رمز بداية، و ε حقل فارغ. كما أن B أو C لا يمكن أن يمثلا رمز بداية. كل لغة بصيغة تشومسكي العادية خالية من السياق، وبالعكس يمكن تحويل كل لغة خالية من السياق إلى لغة بصيغة تشومسكي العادية. وهناك عدة لوغريتمات معروفة للقيام بمثل هذا التحويل. وتوصف التحويلات في أغلب الكتب الدراسية المتخصصة في نظرية الأتمتة، ومنها كتاب هوبكروفت وأولمان (Hopcroft and Ullman, 1979). وكما بيّن لانغ ولايس، فإن العيب في هذه التحويلات هو أنها قد تؤدي إلى مط غير مرغوب في حجم اللغة. وباستخدام | G | للرمز إلى حجم اللغة الأصلية G، فإن حجم المط في أسوأ الحالات قد يتراوح ما بين | G | 2 إلى 22 (ar)
- 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. (ca)
- 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. (cs)
- 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. (en)
- 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. (de)
- 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 . (it)
- 言語の理論（形式言語の理論）において、次のような生成規則のみからなる文法をチョムスキー標準形（チョムスキーひょうじゅんけい）という。 または または ここで、A 、 B および C は非終端記号、α は終端記号であり、Sは開始記号を表し、ε は空列を表すものとする。 また、チョムスキー標準形には次のような性質が挙げられる。
* チョムスキー標準形で表すことのできる文法は全て文脈自由であり、また全ての文脈自由文法は、これと等価なチョムスキー標準形の文法に書き換えることができる。
* S→ε型の規則（空列を導出する文法に含まれる）を除いて、チョムスキー標準形の文法における全ての生成規則は拡張的である。つまり、終端記号と非終端記号からなる文字列に生成規則を適用して生成される文字列の長さは元の文字列の長さよりも等しいか、あるいは長くなる。
* 長さ n の文字列を導出するには、2n-1 回以上規則を適用する必要がある。
* 1つの非終端記号から導出される非終端記号は常に2つとなり、構文木は二分木で表されるため、木の深さは最大でも文字列の長さである。 チョムスキー標準形の名前はノーム・チョムスキーにちなむ。 (ja)
- 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. (nl)
- 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. (pl)
- 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. (pt)
- Нормальная форма Хомского — свойство формальной грамматики, если все её продукции имеют вид: или или, где , и — нетерминалы, — терминальный символ (представляющий постоянное значение), — начальный символ, и — пустая строка. Также ни , ни не может быть начальным символом. Каждая грамматика в нормальной форме Хомского является контекстно-свободной, и наоборот, каждая контекстно-свободная грамматика может быть эффективно преобразована в эквивалентную грамматику в нормальной форме Хомского. Названа по имени Ноама Хомского, американского лингвиста, предложившего иерархию Хомского. (ru)
|
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)