Sipser: Section 2.1

From CSWiki

Jump to: navigation, search

CSC 341: Front Door


CSC 341: Cooperative commentary | Sipser:_Chapter_2

Formal Definition of a Context-Free Grammar

From Definition 2.2 on page 104, a context-free grammar is a 4-tuple (V, Σ, R, S), where

 V   a finite set called the variables.
 Σ   a finite set, disjoint from V, called the terminals.
 R   a finite set of rules.
 S \in V is the start variable.

Formally, we can think of the rules as ordered pairs, where the first element of each rule is a variable, and the second is a string composed of variables and terminals (or possibly the empty string).

Chomsky Normal Form

Chomsky Normal Form (hereafter CNF) is a simplified form of Context Free Grammars useful for applying algorithms. Any context-free language can be generated by a CNF grammar (Theorem 2.9), so CFGs and CNF grammars are exactly equivalent. A grammar is in CNF if every variable yields either any two variables, except the start variable, or one terminal. In addition, the start variable may yield \varepsilon. The process for converting a CFG to CNF is given on pp. 107-109.

The people behind the theory

Chomsky Normal form is (to the best of my knowledge) named for "Noam Chomsky", a preeminent linguist at MIT who, incidentally, has some fairly radical political views.


CSC 341: Front Door

Personal tools