Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Chomsky_normal_form> ?p ?o. }
Showing items 1 to 37 of
37
with 100 items per page.
- Chomsky_normal_form abstract "In formal language theory, a context-free grammar is said to be in Chomsky normal form (named for Noam Chomsky) if all of its production rules are of the form: or or ,where , and are nonterminal symbols, is a terminal symbol (a symbol that represents a constant value), is the start symbol, and is the empty string. Also, neither nor may be the start symbol, and the third production rule can only appear if is in , namely, the language produced by the context-free grammar .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. Several algorithms for performing such a transformation are known. Transformations are described in most textbooks on automata theory, such as Hopcroft and Ullman, 1979. As pointed out by Lange and Leiß, the drawback of these transformations is that they can lead to an undesirable bloat in grammar size. The size of a grammar is the sum of the sizes of its production rules, where the size of a rule is one plus the length of its right-hand side. Using to denote the size of the original grammar , the size blow-up in the worst case may range from to , depending on the transformation algorithm used.".
- Chomsky_normal_form wikiPageExternalLink cnf.pdf.
- Chomsky_normal_form wikiPageID "7850".
- Chomsky_normal_form wikiPageRevisionID "600254123".
- Chomsky_normal_form hasPhotoCollection Chomsky_normal_form.
- Chomsky_normal_form subject Category:Formal_languages.
- Chomsky_normal_form subject Category:Noam_Chomsky.
- Chomsky_normal_form type Abstraction100002137.
- Chomsky_normal_form type Communication100033020.
- Chomsky_normal_form type FormalLanguages.
- Chomsky_normal_form type Language106282651.
- Chomsky_normal_form comment "In formal language theory, a context-free grammar is said to be in Chomsky normal form (named for Noam Chomsky) if all of its production rules are of the form: or or ,where , and are nonterminal symbols, is a terminal symbol (a symbol that represents a constant value), is the start symbol, and is the empty string.".
- Chomsky_normal_form label "Chomsky normal form".
- Chomsky_normal_form label "Chomsky-Normalform".
- Chomsky_normal_form label "Chomsky-normaalvorm".
- Chomsky_normal_form label "Forma Normal de Chomsky".
- Chomsky_normal_form label "Forma normal de Chomsky".
- Chomsky_normal_form label "Forme normale de Chomsky".
- Chomsky_normal_form label "Postać normalna Chomsky'ego".
- Chomsky_normal_form label "Нормальная форма Хомского".
- Chomsky_normal_form label "نموذج تشومسكي الطبيعي".
- Chomsky_normal_form label "チョムスキー標準形".
- Chomsky_normal_form label "乔姆斯基范式".
- Chomsky_normal_form sameAs Chomského_normální_forma.
- Chomsky_normal_form sameAs Chomsky-Normalform.
- Chomsky_normal_form sameAs Forma_normal_de_Chomsky.
- Chomsky_normal_form sameAs Forme_normale_de_Chomsky.
- Chomsky_normal_form sameAs チョムスキー標準形.
- Chomsky_normal_form sameAs Chomsky-normaalvorm.
- Chomsky_normal_form sameAs Postać_normalna_Chomsky'ego.
- Chomsky_normal_form sameAs Forma_Normal_de_Chomsky.
- Chomsky_normal_form sameAs m.0269p.
- Chomsky_normal_form sameAs Q1076039.
- Chomsky_normal_form sameAs Q1076039.
- Chomsky_normal_form sameAs Chomsky_normal_form.
- Chomsky_normal_form wasDerivedFrom Chomsky_normal_form?oldid=600254123.
- Chomsky_normal_form isPrimaryTopicOf Chomsky_normal_form.