CS 301 Spring 2012 Problem Set 4

1. Prove that every finite language must be regular. (Hint: Use induction on the size of the language.)
2. Consider the class C of all languages that are both regular and infinite. For each of the following, tell whether class C is closed, and if it is not closed, give a brief counterexample:
   1. Union
   2. Intersection
   3. Kleene Star
3. For each of the following languages, tell whether it is regular or not, and prove your answer. (One way to show a language is regular is by giving an automaton or by giving a regular expression. Almost always, to show a language is not regular, you will use the Pumping Lemma.)
   1. \{ 0^i 1^j : i, j \geq 0 \mbox{ and } i + j = 4 \}
   2. \{ 0^i 1^j : i, j \geq 0 \mbox{ and } i - j = 4 \}
   3. \{ 0^i 1^j : i, j \geq 0 \mbox{ and } |i - j| = 4 \}
   4. \{ 0^i 1^j : 0 \leq i \leq j \leq 42 \}
   5. \{ w \in (a \cup b \cup c)^* : n_a(w) \cdot n_b(w) \geq n_c(w) \} where n_x(w) denotes the number of times that character x appears in string w .
   6. \{ a^i b^j a^i : i, j \geq 0 \}
4. Give an algorithm for determing whether a regular expression R over alphabet {a, b} denotes a language that includes a string with aaa as a substring. (So the answer should be yes if the language contains baaabbaab even if the language does not contain the string aaa itself.)