Theoretical Foundations of Computing

  1. Read [Sip12] Chapter 0; you may need to review the prerequisite materials in discrete mathematics to have sufficient
    working knowledge for this course.
  2. Do [Sip12] Chapter 1, exercise 1.18 (h) and (i) (in exercise 1.6). Justify your solutions by properly structuring
    and annotating your regular expressions.
  3. Do [Sip12] Chapter 1, exercise 1.29 (b).
  4. Do [Sip12] Chapter 1, problem 1.53.
  5. Prove or disprove that the following languages are regular.
    (a) {uvur
    | u, v ∈ (0 ∪ 1)+}.
    (b) {uurv | u, v ∈ (0 ∪ 1)+}.
  6. Using the closure properties of regular sets and the fact that the language {a
    nb
    n | n ≥ 0} is not regular, prove
    that the language {w ∈ {a, b}

    | #a(w) 6= #b(w)} is not regular. This part is not graded since it was covered in
    lecture. Do the part below.
    Prove that the above language L is non-regular by a direct application of Pumping Lemma.
  7. Consider the following two languages over the alphabet {0, 1}:
    L1 = {1
    nx | x ∈ {0, 1}

    and x contains at least n 1s, for n ≥ 1},
    L2 = {1
    nx | x ∈ {0, 1}

    and x contains at most n 1s, for n ≥ 1}
    Study the regularity of the languages L1 and L2.
  8. For each of the following languages, construct a context-free grammar generating the language; briefly and precisely
    describe the strings generated by each variable in the grammar. Notes: You should aim to give the simplest
    grammars possible, and offer brief explanations about how your grammars work.
    (a) {a
    i
    b
    j
    | i, j ≥ 1, and |i − j| ≤ 3}.
    (b) {a
    i
    b
    j
    | i, j ≥ 0, and i 6= j}.
    (c) {x1x2cy | x1, x2, y ∈ {a, b}

    , and there exists x ∈ {a, b}
    ∗ with x1xx2 = y
    r}.
    (d) {w ∈ {0, 1}

    | the number of 0s in w is a multiple of 3, and w is a palindrome}.

Sample Solution

ACED ESSAYS