SOLVED COMP 335 Introduction to Theoretical Computer Science Assignment 3

1. [20 Points] For each of the following languages over Σ = {a, b}, write a regular grammar and then convert it into an equivalent NFA using the procedure described in class. (a) (10 Points) L(r) where r = ((a + b)(a + b))∗ b + a((a + b)(a + b))∗ ; and (b) (10 Points) {w ∈ {a, b} ∗ : w ends in a and |w| ≡ 1 (mod 3)}. 2. [25 Points] Fix an alphabet Σ. For any string w with |w| ≥ 2, let skip(w) be the string obtained by removing the first two symbols of w. Define two operators on languages: f1(L) = {w ∈ Σ ∗ : skip(w) ∈ L}, and f2(L) = {skip(w) ∈ Σ ∗ : w ∈ L} (a) (5 Points) Consider L 0 = L(bba∗ ) over the alphabet Σ = {a, b}. Write a regular expression representing f1(L 0 ). Write another regular expression representing f2(L 0 ). (b) (10 Points) Claim: for every regular language L the language f1(L) is regular. Clearly state whether the claim is TRUE or FALSE, and then prove your answer. (c) (10 Points) Claim: for every regular language L the language f2(L) is regular. Clearly state whether the claim is TRUE or FALSE, and then prove your answer. 3. [20 Points] For each of the following languages, use the Pumping Lemma and/or closure properties of regular languages to show that the language is not regular. (a) (10 Points) L1 = {0 k1 ` : k ≥ ` 4 ≥ 0}. (b) (10 Points) L2 = {a n : n is not a perfect cube}.