CS 332: Theory of Computation Professor Mark Bun Boston University January 27, 2020
Homework 1 – Due Monday, February 3, 2020 before 2:00PM
Reminder Collaboration is permitted, but you must write the solutions by yourself without assis- tance, and be ready to explain them orally to the course staff if asked. You must also identify your collaborators. Getting solutions from outside sources such as the Web or students not enrolled in the class is strictly forbidden.
Exercises Please practice on exercises and solved problems in Chapters 1. The material they cover may appear on exams. It’s also a good idea to practice constructing DFAs and NFAs for specific languages using http://automatatutor.com/.
Problems There are 3 mandatory problems and one bonus problem.
1. Give state diagrams of DFAs with as few states as you can recognizing the following languages.
(a) L1 = {w | w begins with 10 and ends with 11}.
(b) L2 = {w | w represents a binary number that is congruent to 2 modulo 3}. In other words, this number minus 2 is divisible by 3. The number is presented starting from the most sig- nificant bit and can have leading 0s.
(c) L3 = {w | w is a string of the form x1y1x2y2 . . . xnyn for some natural number n such
that if x is the integer with binary representation x1x2 . . . xn and y is the integer
with binary representation y1y2 . . . yn then x > y}. Both x and y are presented starting from the most significant bit and can have leading 0s.
(d) L4 = {w | w represents a possible series of flips in the game in which player 1 wins
where H represents heads and T represents tails} where the game goes like this: Repeatedly flip a coin. On heads, player 1 gets a point. On tails, player 2 gets a point. A player wins (and the game ends) as soon as they are ahead by two points.
Give state diagrams of NFAs with as few states as you can recognizing the following languages:
(e) L5 ={w|thethirdsymbolfromtheendinwis0}.
(f) L6 = {w | w contains substrings 100 and 00 which do not overlap}.
2. In class, we have shown that if M is a DFA that recognizes a language A then we can obtain a DFA M′ that recognizes A by swapping accept and non-accept states in M.
(a)
(b) 3. (a)
Show, by giving an example, that if M is an NFA that recognizes a language B then we do not necessarily obtain an NFA recognizing B by swapping accept and non-accept states in M.
Is the class of languages recognized by NFAs closed under complement? Explain your answer.
Givenastringwof0sand1s,theflipofwisobtainedbychangingall0sinwto1sandall 1sinwto0s. GivenalanguageA,theflipofAisthelanguage{w|theflipofwisinA}. Prove that the class of regular languages is closed under the flip operation.
1
(b) Given languages A and B over alphabet Σ, the interleaving of A and B is defined as {w | w = a1b1 …akbk, where a1 …ak ∈ A and b1 …bk ∈ B, each ai,bi ∈ Σ∗}.
Prove that the class of regular languages is closed under interleaving. Be careful: each ai, bi is a (possibly empty) string of symbols.
4. Bonus problem, no collaboration is allowed
Let’s consider a function f : Σ → Γ∗ from one alphabet to strings over another alphabet. A
fuction of this type is called a homomorphism.
We can extend the domain of this function to all strings over alphabet Σ by defining f(w) = f(w1)f(w2)…f(wn), where w = w1w2 …wn and wi ∈ Σ if w is not empty, and f(ε) = ε in case it is. We also can further extend f to operate on languages by defining f(A) = {f(w) | w ∈ A}, for any language A.
Show, by giving a formal construction, that the class of regular languages is closed under homo- morphism. In other words, given a DFA M that recognizes B and a homomorphism f, construct a finite automaton N that recognizes f(B). Consider the machine N that you constructed. Is it a DFA in every case?
2