CS 334: Problem Set 2.
Problem 1. (10 points) Give regular expressions to generate each of the following languages.
a) {𝑤 ∈ {𝑎, 𝑏}
∗
∶ 𝑤 does not end in 𝑏𝑎}
b) {𝑤 ∈ {0,1}
∗
: 𝑤 = 𝛼 ∘ 𝛽 and α has an even number of 1
′
s and β has an even number of 0
′
s}
Problem 2. (10 points) Similar to an NFA in structure, an OFA (obsessive finite state machine) is
one that accepts an input string if and only if every possible final state after the entire input
state has been processed is an accept state of the machine. In other words, every computation
path that does not die must end in an accept state. Prove that OFAs recognize all and only
regular languages.
Problem 3. (10 points) For each of the following statements either argue that it is true, or else
give a counterexample.
a) Every finite language is regular.
b) If every state of an NFA is an accept state then its language is Σ
∗
c) If a k-state DFA accepts a string of length k then its language is infinite.
d) Regular languages are closed under union and intersection and the difference
operator.
e) If every state of an NFA for language L is flipped then the new NFA accepts the
complement of L.
f) If every state of an NFA is flipped then the language accepted is not necessarily
regular.
Problem 4. (20 points) Give a regular expression to describe the language of the following DFA.
Use the DFA to regular expression conversion theorem and show all steps of your conversion.
𝑏
𝑎
𝑏
𝑏
𝑎
𝑎
𝑏
𝑎
