CSC 341: February 12, 2007

Instructor's notes for the class session

Leftmost derivations; the bijection between leftmost derivations and derivation trees

Ambiguity: a property of grammars

Inherent ambiguity. Show that $\{\texttt{a}^i \texttt{b}^j \texttt{c}^k \mid i = j \vee j = k\}$ is inherently ambiguous.

Constraining the form of rules still further.

Theorem 2.9: Every context-free language is generated by some context-free grammar in Chomsky normal form.

The algorithm for reducing a context-free grammar to Chomsky normal form.

Add a new start symbol.
Remove $\varepsilon$ -rules.
Remove unit rules.
Remove rules with three or more symbols on the right-hand side.
Rewrite rules with two terminals or a terminal and a variable on the right-hand side.

As an example, do Exercise 2.14 on page 129 of Sipser's book.

Demonstrate the Chomsky-normal-form module.

Why is it necessary to allow the rule $S \rightarrow \varepsilon$ in a grammar in Chomsky normal form? Why is it sufficient to allow the start symbol, and no other, to be nullable?
If a context-free grammar containing the (superfluous) rule $A \rightarrow A$ is put into Chomsky normal form, this rule will be eliminated atstep 3, since it is a unit rule. But doesn't the same step simply reintroduce exactly the same rule again (since it is of the form $B \rightarrow u$ )? Doesn't this lead to an infinite loop?
Prove that, in a grammar in Chomsky normal form, every derivation of a string of terminals has an odd number of steps.

Any production with $\varepsilon$ on its right-hand side can be eliminated (described in Sipser's proof of Theorem 2.9) without affecting the language that the grammar generates. Therefore, it is sufficient to allow the start symbol to be nullable.
This will not lead to an infinite loop because a new production is added only when it is not a duplicate of a unit rule that is previously removed.
Every rule in a CNF grammar either increases the length of the current string by 1 or replaces a variable with a terminal, but not both. To derive a string of positive length k, then, requires k-1 steps that increase the length of the current string and k steps to replace variables with terminals. Hence, the total number of steps are odd. (Taken from Prof. Stone's comments)