CS 334: Problem Set 1.

Problem 1. (30 points) Construct deterministic FSAs for each of the following languages over

the alphabet {π, π}:

1. πΏ1 = {π€: π€ ππππ‘ππππ π‘βπ π π‘ππππ πππ πππ π‘βπ π π‘ππππ πππ}.

2. πΏ2 = {π€: π€ ππππ‘ππππ ππ ππ£ππ ππ’ππππ ππ π

β²

π πππ πππβ π ππ ππππππ€ππ

ππππππππ‘πππ¦ ππ¦ ππ‘ ππππ π‘ πππ π}

Hint: πΏ2

is the intersection of two languages. Itβs trivial to design an FSA for each of

these. Once you do that, use the construction of Theorem 1.25 (but for intersection

rather than union) to construct the FSA for πΏ2

.

3. πΏ3 = {π€:π‘βπ 3ππ πππ π‘ π π¦ππππ ππ π€ ππ π}.

So, for example, ππππππ β πΏ3 ππ’π‘ ππππππ β πΏ3

. To get started see how trivial it

would be if the FSA had to check the last symbol of the input. Then try to design an FSA

that must check only the 2nd last symbol. What does each state in this FSA represent?

Now extend this idea to design an FSA that accepts πΏ3

.

Problem 2. (10 points) Modify the proof of Theorem 1.25 in the textbook to cover the case

when the machines π1

,π2 have different input alphabets Ξ£1

,Ξ£2

. Hint: the machine π that

recognizes the union of the languages of π1

,π2 will have input alphabet Ξ£ = Ξ£1 βͺ Ξ£2

. Take

care when defining πΏ((π1

, π2

), π) as the symbol π could belong to one alphabet but not the

other!

Optional Problem. (Present your solution anytime this term to Sandeep for credit.) Suppose

that you are asked to design an FSA to operate a building elevator. How would you go about

this design process? What would a state of the FSA correspond to? What should be the

alphabet? What constraints would be reasonable to impose on the movement of the elevator?

This is an open-ended problem β we donβt expect a full design, but rather things you considered

and what constraints you found difficult to design for. To get started, imagine a 2-storey

building, then a 3-storey building, etc.

Sale!