CS 334: Problem Set 2


Rate this product

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 𝑆𝐻𝐼𝐹𝑇(𝐿) = {𝑆𝐻𝐼𝐹𝑇(𝜎): 𝜎 ∈ 𝐿}.

Open chat
Need help?
Can we help you?