CSC444 Homework #4

Exercises to Submit

1. Convert the following context-free grammar to Chomsky normal form following the algorithm of Theorem 2.9 on pages 107-108, showing the steps taken to reach the final result.

        S -> A
        A -> a A b | B
        B -> c B | ε
   
   

2. Problem 2.26 on page 130. If v is any sentence of length n >= 1 in the language of a grammar in Chomsky normal form, then there are exactly 2n-1 steps in any derivation of v.

   ---

   Here is an outline of how to prove the result.

   1. First, recall the notation defined on page 102 of the text:

      u =>^* v

      means the string u derives the string v in 0 or more steps, where u and v strings of terminals and or non-terminals.

      If u is the start symbol of the grammar, v is called a sentential form.

      If u is the start symbol and v consists only of terminals, then v is not only a sentential form but also a sentence in the language of the grammar.

   2. Now, for the method of the proof:

      Let P_n be the statement:

      If for a context-free grammar G = (V,T,S,R),

      1. u =>^* v for u in V and v in T^*, and
      2. v has length n, and
      3. G is in Chomsky normal

      then the number of steps in u =>^* v is 2n-1.

   3. What to prove.

      Prove P_n is true for all n >=1.

      Use induction on n.

      Note that the u in the statements P_n is restricted to be any single non-terminal, not a general string of grammar symbols. But even with this restriction, the general result that statements P_n are true (once proved), can still be applied to the case that u is the start symbol and v is a sentence in the language of the gramamr, showing that any sentence of length n in a grammar in Chomsky normal form, must have a derivation with exactly 2n - 1 steps.

   4. Hint

      For the inductive step you may find this fact useful:

      If the number of steps in a derivation u =>^* v is > 1, then since G is in Chomsky normal form, the first step in the derivation must be of the form u => XY for two non-terminals X and Y and we can write

      u => XY =>^* v₁v₂ = v where X =>^* v₁ and Y =>^* v₂

      for some non-terminals X and Y and strings v₁ and v₂.

Exercises Not Submitted

These exercises will not be collected, but try to find a solution. They will be discussed in class. Fame and glory may be given for good solutions.

1. Exercise 2.2, page 128
2. Exercise 2.3 (No fame or glory. The answer is in the book.)
3. Exercise 2.4e
4. Exercise 2.6b
5. Describe a pushdown automaton that recognizes this language:

   All strings in {a,b} that have the same number of a's as b's. The a's and b's can be in any order, but the total number of a's must equal the total number of b's. The null string is in this language.

6. Give a context free grammar for the language in the previous problem.