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

quote
You can use as reference:Text: Introduction to the Theory of Computation 3rd Edition Author: Michael Sipser ISBN-13: 978-1133187790 ISBN-10: 113318779X Publisher: Cengage Learning



COT-5310 Theory of Computation I Assignment 2 Florida International University 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. (10 points) Convert the NFA below to its equivalent DFA: q0start q1 q2 0 ε 0 0,1 4. (25 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 } 1 (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} 5. (5 points) Formally prove that every finite language is regular (Hint: Use proof by induction on the cardinality of an arbitrary finite language, and the theorem that say every regular language can be described by a regular expression). 6. (5 points) Use pumping lemma to show that {0n1m|0 ≤ n ≤ m} is not a regular language. 7. (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+} (c) { apb2+qa2 ∈ {a, b}∗ ∣∣∣ p, q ∈ Z+} 8. (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