About: Chomsky normal form

Facets (new session)
Description
Metadata
Settings
- Rule:
- Inverse Functional Properties:
- "Same As":

About: Chomsky normal form Goto Sponge NotDistinct Permalink

An Entity of Type : dbo:Country, within Data Space : el.dbpedia.org associated with source document(s)

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.

Attributes	Values
rdf:type	Thing country
rdfs:label	Chomsky normal form (en)
rdfs:comment	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)
differentFrom	Conjunctive normal form
sameAs	Chomsky normal form Chomsky normal form
dbp:wikiPageUsesTemplate	dbt:Citation_needed dbt:Cite_book dbt:Color dbt:Distinguish dbt:Reflist dbt:Rp dbt:Ya dbt:Aye dbt:Na dbt:Nay dbt:Diagonal_split_header dbt:Noam_Chomsky
Subject	Formal languages Noam Chomsky
Link from a Wikipage to an external page	https://archive.org/details/introductiontoth00sips https://books.google.com/books%3Fid=a-rjBwAAQBAJ&q=%22Chomsky+normal+form%22%7Cdate=6 http://cs.nyu.edu/courses/fall07/V22.0453-001/cnf.pdf
thumbnail	wiki-commons:Special:FilePath/Syntax_tree_of_arithmetic_expression_wrt_Chomsky_normal_form_grammar.gif?width=300
foaf:depiction
gold:hypernym	Symbols
prov:wasDerivedFrom	http://en.wikipedia.org/wiki/Chomsky_normal_form?oldid=1070697034&ns=0
Wikipage page ID	7850 (xsd:integer)
page length (characters) of wiki page	19330 (xsd:nonNegativeInteger)
Wikipage revision ID	1070697034 (xsd:integer)
Link from a Wikipage to another Wikipage	Formal grammar Formal language Greibach normal form Noam Chomsky Production (computer science) ALGOL 60 Backus–Naur form Bottom-up parsing CYK algorithm C (programming language) Formal languages Noam Chomsky Donald Knuth Kuroda normal form Pumping lemma for context-free languages Robert W. Floyd Terminal and nonterminal symbols Compiler Context-free grammar Parsing Empty string Equivalence (formal languages) Exponentiation Inline expansion
has abstract	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. (en)
foaf:isPrimaryTopicOf	http://en.wikipedia.org/wiki/Chomsky_normal_form
is differentFrom of	Conjunctive normal form
is Wikipage redirect of	Chomsky Normal Form
is Link from a Wikipage to another Wikipage of	Greibach normal form Normal form Backus–Naur form CNF CYK algorithm Kuroda normal form Chomsky (disambiguation) Chomsky Normal Form Computational linguistics Context-free grammar Context-free language List of algorithms Index of computing articles Index of philosophy articles (A–C)
is foaf:primaryTopic of	http://en.wikipedia.org/wiki/Chomsky_normal_form

Faceted Search & Find service v1.17_git151 as of Feb 20 2025

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Nov 11 2024, on Linux (x86_64-ubuntu_focal-linux-gnu), Single-Server Edition (72 GB total memory, 933 MB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2025 OpenLink Software