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.
