CS 334: Problem Set 1.

CS 334: Problem Set 1.
Problem 1. (10 points) Construct deterministic FSAs for each of the following languages over
the alphabet {𝑎, 𝑏}:
1. 𝐿1 = {𝑤: 𝑤 𝑐𝑜𝑛𝑡𝑎𝑖𝑛𝑠 𝑡ℎ𝑒 𝑠𝑡𝑟𝑖𝑛𝑔 𝑎𝑎𝑎 𝑜𝑟 𝑡ℎ𝑒 𝑠𝑡𝑟𝑖𝑛𝑔 𝑏𝑏𝑏}
2. 𝐿2 = {𝑤: 𝑤 𝑐𝑜𝑛𝑡𝑎𝑖𝑛𝑠 𝑡ℎ𝑒 𝑠𝑡𝑟𝑖𝑛𝑔 𝑎𝑎𝑎 𝑎𝑛𝑑 𝑡ℎ𝑒 𝑠𝑡𝑟𝑖𝑛𝑔 𝑏𝑏𝑏}
Problem 2. (10 points) With the soccer season upon us, you have been selected to design the
finite state controller for scoring penalty shootouts. The rules for a penalty shootout are as
follows:
1. In every round the visitors shoot first, followed by the home team. Each goal scored
earns one point.
2. If, at the end of 5 rounds the teams are tied then more rounds are played.
3. The game ends as soon as at least 5 rounds have been played and the scores are
different at the end of the last round played.
4. The team with more total points at the end wins the game.
Design an FSA for scoring penalty shootouts. The FSA must accept shootouts corresponding to
a win for the home team (presumably to set off the fireworks display) and reject all nonwinning plays. Be sure to specify all components of your FSA in detail.
Problem 3. (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!
Problem 4. (10 points) Let 𝐷𝑘 denote the set of binary strings that represent numbers divisible
by 𝑘. For example, input strings 0, 00, 000, 10, 010, 0010, 0100010 are all divisible by 2 (the
least significant bit is the rightmost, or last symbol in the sequence), and therefore are all in the
language 𝐷2.
1. Construct a deterministic FSA to recognize the language 𝐷3. Hint: As you process the
input use a state to maintain the value of the remainder of the input processed thus far.
2. Prove that 𝐷𝑘 is regular, for every 𝑘 ≥ 1.
Problem 5. Optional, and extra credit. (10 points) 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.