PlanetMath (more info)
 Math for the people, by the people. Sponsor PlanetMath
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: Very high Entry average rating: No information on entry rating
[parent] 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)

View style:

See Also: Greibach normal form, Kuroda normal form


This object's parent.
Log in to rate this entry.
(view current ratings)

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 MSC68Q45 (Computer science :: Theory of computing :: Formal languages and automata)
 68Q42 (Computer science :: Theory of computing :: Grammars and rewriting systems)

Pending Errata and Addenda
None.
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)