Description

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

Question 1. (18 points) Give DFAs for the following languages.
(a) A = {x ∈ {0,1}∗ | #0(x) ≤ 2 and #1(x) ≥ 1}
(b) B = {x ∈ {0,1}∗ | x does not contain the substring 1011}
(c) C = {x ∈ {0,1}∗ | x has at least 3 occurrences of 3 consecutive 1’s with overlapping}
(For example the string 11111 is in the language C.)
Question 2. (12 points) Give DFAs accepting the same language as the following regular expressions using the minimum number of states. Give reason why you cannot have a DFA with lesser number of states. (a) (0 + 1(01∗0)∗1)∗
(b) (000∗ + 111∗)∗
Question 3. (10 points) For languages L1 and L2 over Σ, define
Mix(L1,L2) = {w ∈ Σ∗ | w = x1y1x2y2 …xkyk, where x1x2 …xk ∈ L1 and y1y2 …yk ∈ L2, each xi,yi ∈ Σ∗}.
Show that if L1 and L2 are regular then Mix(L1,L2) is also regular.
Question 4. (10 points) Let Σ and ∆ be two alphabets and let h : Σ → ∆∗. Extend h to be a function from Σ∗ to ∆∗ as follows:
) where w ∈ Σ∗, a ∈ Σ.
(Such a function h is called a homomorphism.)
Now, for L ⊆ Σ∗, h(L) = {h(w) ∈ ∆∗ | w ∈ L}.
Also, for L ⊆ ∆∗,
h−1(L) = {w ∈ Σ∗ | h(w) ∈ L}.
(a) Prove that if L ⊆ Σ∗ is regular, then so is h(L).
(b) Prove that if L ⊆ ∆∗ is regular, then so is h−1(L).
Page 1 of 1