# Chomsky normal form

A grammar is said to be of *Chomsky normal form* if every production
has either of the two forms

$$A\to BC\mathit{\hspace{1em}\hspace{1em}}\text{or}\mathit{\hspace{1em}\hspace{1em}}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.

Title | Chomsky normal form |
---|---|

Canonical name | ChomskyNormalForm |

Date of creation | 2013-03-22 16:21:13 |

Last modified on | 2013-03-22 16:21:13 |

Owner | rspuzio (6075) |

Last modified by | rspuzio (6075) |

Numerical id | 7 |

Author | rspuzio (6075) |

Entry type | Definition |

Classification | msc 68Q42 |

Classification | msc 68Q45 |

Related topic | GreibachNormalForm |

Related topic | KurodaNormalForm |