# 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.)
-- Main.sloan - 2012-02-04

This topic: CS301 > WebHome > Syllabus > Homeworks > ProblemSet4
Topic revision: r3 - 2012-02-05 - 03:18:47 - Main.ctanti2

 Copyright 2016 The Board of Trustees of the University of Illinois.webmaster@cs.uic.edu WISESTHelping Women Faculty AdvanceFunded by NSF  