|
|
|
|
Chomsky normal form
|
(Definition)
|
|
|
A grammar is said to be of Chomsky normal form if every production has either of the two forms $$ A \to BC \qquad \mbox{ or } \qquad A \to a $$ where $A,B,C$ are non-terminal symbols, and $a$ is a terminal symbol.
Grammars of this sort are context-free, hence they describe context-free languages. Moreover, given any context-free language not containing the empty word $\lambda$ , there exists a Chomsky normal form grammar which describes it.
|
"Chomsky normal form" is owned by rspuzio. [ full author list (3) ]
|
|
(view preamble | get metadata)
Cross-references: empty word, context-free languages, context-free, sort, production, grammar
There are 2 references to this entry.
This is version 4 of Chomsky normal form, born on 2006-10-28, modified 2009-05-14.
Object id is 8488, canonical name is ChomskyNormalForm.
Accessed 1859 times total.
Classification:
| AMS MSC: | 68Q45 (Computer science :: Theory of computing :: Formal languages and automata) | | | 68Q42 (Computer science :: Theory of computing :: Grammars and rewriting systems) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|