TWiki> CS301 Web>Syllabus>Homeworks>ProblemSet4 (revision 1)EditAttach

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 .
(More coming shortly.) -- Main.sloan - 2012-02-04
Edit | Attach | Print version | History: r3 < r2 < r1 | Backlinks | Raw View | Raw edit | More topic actions...
Topic revision: r1 - 2012-02-04 - 16:17:55 - Main.sloan
 
Copyright 2016 The Board of Trustees
of the University of Illinois.webmaster@cs.uic.edu
WISEST
Helping Women Faculty Advance
Funded by NSF