Solved–Problem Set 1 –Solution

Description

Problem 1. (10 points) Construct deterministic FSAs for each of the following languages over the alphabet { , }:

1. ₁ = { : ℎ ℎ }

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 non-winning 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 ₁, ₂ have different input alphabets Σ₁, Σ₂. Hint: the machine that recognizes the union of the languages of ₁, ₂ will have input alphabet Σ = Σ₁ ∪ Σ₂. Take care when defining (( ₁, ₂), ) 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 ₂.

1. Construct a deterministic FSA to recognize the language ₃. 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.