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 ππ»πΌπΉπ(πΏ) = {ππ»πΌπΉπ(π): π β πΏ}.

Sale!