Homework 8

CS 3810 – Summer 2008

  1. Convert the following grammar to a one state PDA.

S → bA

S → aB

A → a

B → b

A → aS

B → bS

A → bAA

B → aBB



  1. Use the Pumping Lemma for CFLs to show the following languages are not context free.

    1. L = { ambmcn | m < n }

    2. L = { wwRw | w ∈ (a+b)* }

  2. For each of the following languages, specify whether the language is (i) regular, (ii) context-free, but not regular, or (iii) not context free. Justify your answer.

    1. { w in (a+b)* | each symbol appears the same number of times }

    2. { w in (a+b+c)* | each symbol appears the same number of times }

    3. { ambn | 5m + 4n = 44 }