Problem Set #1

CS 154
due September 16, 2004

Each problem is worth 10 points.

 

  1. Give two different examples of DFAs that accept the language 0(10)* over the alphabet {0,1}.

  2. Give an example of a DFA that accepts exactly those strings over {0,1,2} that do not contain 110 as a substring.

  3. Prove by induction that |xn| = n|x|, where |y| denotes the length of the string y. You may use any theorem proved in class.