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
WISEST
Helping Women Faculty Advance
Funded by NSF