CS 301 Spring 2012 Problem Set 4
- Prove that every finite language must be regular. (Hint: Use induction on the size of the language.)
- 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:
- Union
- Intersection
- Kleene Star
- 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.)
- \{ 0^i 1^j : i, j \geq 0 \mbox{ and } i + j = 4 \}
- \{ 0^i 1^j : i, j \geq 0 \mbox{ and } i - j = 4 \}
- \{ 0^i 1^j : i, j \geq 0 \mbox{ and } |i - j| = 4 \}
- \{ 0^i 1^j : 0 \leq i \leq j \leq 42 \}
- \{ 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 .
- \{ a^i b^j a^i : i, j \geq 0 \}
- Give an algorithm for determing whether a regular expression R over alphabe {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.)
-- Main.sloan - 2012-02-04
Topic revision: r2 - 2012-02-04 - 17:36:10 - Main.sloan