Description

CSE340: Theory of Computation (Homework Assignment 2)
Total Number of Pages: 1 Total Points 40

Question 1. (5 points) Give a regular expression for the following language.
B = {x ∈ {0,1}∗ | x does not contain the substring 101}
Question 2. (5 points) Prove that {0i1j | gcd(i,j) = 1} is not regular?
Question 3. (6 points) Let A ⊆ N be a subset of natural numbers. A is said to be ultimately periodic if there exists numbers p > 0 and n ≥ 0, such that for all m ≥ n, m ∈ A if and only if m+p ∈ A. In other words, after a certain point (the number n) the numbers in the set A occur in a fixed regular interval of length p.
Consider L ⊆ {a}∗. Prove that L is regular if and only if the set {m | am ∈ L} is ultimately periodic.
(Hint: Think how will the DFA of a unary regular language look like.)
Question 4. (12 points) Give CFGs for the following languages
(a) L1 = {aibjckdl | i,j,k,l ≥ 1, i = l, j = k}
(b) L2 = {anbm | n,m ≥ 0, n 6= m}
(c) L3 = {aibjck | i,j,k ≥ 0, i > j or j > k}
Question 5. Consider the following CFG G over the set of terminals T = {+,∗,0,1,(,)}
S −→ S + S | S ∗ S | (S) | 0 | 1
(a) (2 points) Give a string of length 5 that is ambiguous with respect to G.
(b) (4 points) Give two parse trees for the string in part (a) with respect to G.
(c) (6 points) Give an unambiguous CFG for the language generated by the above grammar that gives proper precedence to the operators (i.e. highest precedence to brackets followed by the ∗ operator and then the + operator).
Page 1 of 1