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 ∈ {a,b}∗ | x alternates between a and b and has at least 2 a’s}
(b) B = {x ∈ {a,b}∗ | x has ababb as a substring}
(c) C = {x ∈ {0,1}∗ | x has at most 2 occurrences of 3 consecutive 1’s with possible overlapping}
(For example the string 1111 is in the language C but the string 11111 is not 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 possible.

(b) (a∗b∗ + b∗a∗)
Question 3. (10 points) For two language A and B over Σ, define f(A,B) = {w ∈ Σ∗ | w = a1b1a2b2 …akbk, where a1,a2,…,ak ∈ A and b1,b2,…,bk ∈ B and each ai,bi ∈ Σ∗}.
Show that if A and B are regular then f(A,B) is also regular.
Question 4. (10 points) Find the minimum-state finite automaton corresponding to the following DFA. Show in details all the steps of minimization.

Page 1 of 1