Sale!

# CS 334: Problem Set 1

\$30.00

Category:
Rate this product

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.

Hello