COT-5310 Theory of Computation I Assignment 2 Florida International University Knight Foundation School of Computing and Information Sciences 1. (10 points) Find an equivalent NFA for the following...

Solution for Theory of Computation I for assignment number 2.



COT-5310 Theory of Computation I Assignment 2 Florida International University Knight Foundation School of Computing and Information Sciences 1. (10 points) Find an equivalent NFA for the following regular expression in the alphabet Σ = {0, 1}: ( 0Σ+1(0 ∪ 10) ∪ 0(1 ∪ ε)Σ∗0 )∗ 2. (10 points) Convert the DFA below into a regular expression that describes exactly the same language. Eliminate states in the following order: q3, q1, q2. Show your work. q0start q1 q2 q3 0 1 1 0,1 0 1 3. (35 points) Find a regular expression which recognizes each of the following languages (in parts (b) and (c), assume that Σ is an arbitrary non-empty finite set of symbols and n is an arbitrary positive integer): (a) { w ∈ {a, b, c}∗|w contains at most two a’s and at most two b’s } (b) { w ∈ Σ∗| the length of w is at most n } (c) { w ∈ Σ∗| the length of w is not equal to n } (d) {w ∈ {a, b, c}∗| (every odd position of w is b or c) ∨ (every even position of w is a)} (e) {w ∈ {0, 1}∗|w 6= 0100 ∧ w 6= 101} 4. (10 points) Use pumping lemma to show that {0n1m|0 ≤ n ≤ m} is not a regular language. 5. (25 points) Are the following languages regular? (Prove your answers) (a) { a( n 2) ∈ {a}∗ ∣∣∣ n ∈ Z≥2} (b) { apbqab √ pqc ∈ {a, b}∗ ∣∣∣ p, q ∈ Z+} 1 (c) { apb2+qa2 ∈ {a, b}∗ ∣∣∣ p, q ∈ Z+} 6. (10 points) Let f : R+ 7→ R+ be a differentiable function and ∀x ∈ R+, f ′(x) ≥ dxe. Prove that {1df(n)e|n ∈ Z+} is not regular (Hint: use pumping lemma). 2