CS 334: Problem Set 2

CS 334: Problem Set 2.
Problem 1. (10 points)
a. Express the following language defined over the alphabet {𝑎,𝑏} as the intersection of
two simpler languages: {𝑤: 𝑤 ℎ𝑎𝑠 𝑎𝑛 𝑜𝑑𝑑 𝑛𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑎
′
𝑠 𝑎𝑛𝑑 𝑒𝑛𝑑𝑠 𝑤𝑖𝑡ℎ 𝑏}
b. Construct FSAs for each of the two languages you found in part (a).
c. Use the cross-product method and combine the two FSAs in part (b) to construct an FSA
for the original language.
d. Construct an FSA for the same language with fewer states by merging two of the states
in your FSA in part (c). Explain why you can merge these two states without changing
the language of the FSA.
Problem 2. (10 points) For any string 𝑤 = 𝑤1𝑤2
· · · 𝑤𝑛
, the reverse of 𝑤, written 𝑤
𝑅
, is the
string 𝑤 in reverse order, 𝑤𝑛
· · · 𝑤2𝑤1
. For any language 𝐴, let 𝐴
𝑅 = {𝑤
𝑅|𝑤 ∈ 𝐴}.
Show that if 𝐴 is regular, so is 𝐴
𝑅
.
Problem 3. (10 points)
a. Construct an FSA with 6 states to recognize 𝐿4 = {1111}. Can you reduce the number
of states below 6? (Hint: recall a basic property of directed graphs from CS 135!)
b. Use your argument to prove that, for all 𝑘 ≥ 3 there is a language that can be accepted
by a 𝑘-state FSA that cannot be recognized by any FSA with fewer states.
Optional Problem. (10 points) For any string 𝜎, over alphabet Σ, we define the string
𝑆𝐻𝐼𝐹𝑇(𝜎) as follows: if 𝜎 = 𝑎𝑤, 𝑎 ∈ Σ, 𝑤 ∈ Σ
∗
then 𝑆𝐻𝐼𝐹𝑇(𝜎) = 𝑤𝑎. For example,
𝑆𝐻𝐼𝐹𝑇(0111) = 1110, 𝑎𝑛𝑑 𝑆𝐻𝐼𝐹𝑇(10110) = 01101.
Prove that if 𝐿 is regular, then so is 𝑆𝐻𝐼𝐹𝑇(𝐿) = {𝑆𝐻𝐼𝐹𝑇(𝜎): 𝜎 ∈ 𝐿}.