Homework 5

CS 3810 – Summer 2008

1. Show that the following sets are not regular. (4 points)

   1. The set PAREN of all balanced strings of parentheses. For example, ( ( ) ( ( ) ) ) is in PAREN, but ( ( ) and ( ) ) ( are not..

   2. {aaaa(b+c)*aaaa | the number of b's and the number of c's are the same}.

2. Exercise 4.2.7 [Closure Properties] (2 points)

3. Exercise 4.2.13 [Closure Properties to Prove Not Regular] (4 points)

4. Algorithms for regular language properties (6 points)

   1. Exercise 4.3.3

   2. Exercise 4.3.4

   3. Exercise 4.3.5

5. Exercise 4.4.2 [Minimization of Automata] (2 points)