## CPS420 |
## W2017 Assignment 3 | |

## Worth: 10% |
## Finite State Automata, Regular Expressions, and Counting |
## Due: Tuesday April 18 |

## Team SizeThis lab can be done in teams of 1 or 2.## Assignment Description## Part A - Automata Construction- Draw a DFA which accepts the following language over the alphabet of {0,1}:
the set of all strings which contain a block of five consecutive symbols which does not contain at least two 0's.
(Hint: Figure out all the final states, label them with the string which causes the acceptance, and then work backwards to the starting state, labelling each intermediate state with the string it is in the process of accepting. The labelling is important in order to not get confused.) - Draw a DFA which accepts the following language over the alphabet of {0,1}:
the set of all strings such that each block of five consecutive symbols contains at least two 0's.
(Hint: look at solution of previous question) - Draw an NFA which accepts the following language over the alphabet of {0, 1, 2, 3, 4,5, 6, 7, 8, 9}:
the set of strings such that the final digit has appeared before.
(Hint: this NFA will be easier to draw vertically - i.e. with vertical transitions - instead of horizontally) - Assuming that you have the following three automata, A
_{1}, A_{2}, A_{3}recognizing the languages L_{1}, L_{2}, L_{3}respectively, shown here as black boxes:
- Draw an NFA called A which recognizes the language L
_{1}(L_{2}| L_{3}) - What is the starting state of A?
- What are A's final states?
- Draw an NFA called A which recognizes the language L
## Part B - Recognizing Automata- Give a precise, concise, and unambiguous English description of the language accepted by this automaton:
- Give a regular expression describing the language accepted by this automaton:
- Give a regular expression describing the language accepted by this automaton:
## Part C - Counting16 swimmers are competing in the Olympic semi-finals for 200m butterfly.- 3 are from Japan,
- 2 each from the US, China, Australia, Brazil, and Hungary
- 1 each from Canada, Spain, and South Africa.
- How many possible outcomes will there eventually be on the podium (by individual swimmer)?
- How many possible podium outcomes by country are there? (in other words we are asking you to figure out how many possible combinations of medals by country there can be) Your answer should not be derived by listing all the possibilities one by one. Instead you should derive your answer by reasoning with known formulas for permutations and combinations. Explain your reasoning.
- Based solely on the number of athletes per country in the semi-finals and not on their relative swimming abilities:
- What is the probability that Canada will earn at least one medal?
- What is the probability that Hungary will earn at least one medal?
- What is the probability that Japan will earn at least one medal?
## References- Textbook chapters 9.1 to 9.6, 9.8, and 12.1 and 12.2
- Handouts and other references can be found in the Lecture Material, including the supplemental handout on NFAs
- In case you want to use it for your answers: Microsoft Visio file used to generate FSAs in this assignment
- You can use the automaton simulator to try ideas out if you want, but I recommend that you use it very sparingly, as it will not be available in the final exam. This is a useful tool, but do not treat it as an indispensable crutch that replaces your own thinking. Such an approach will undermine your learning.
## Hand InThis lab is a paper submission to be handed in at the Computer Science office. If it is inconvenient for you to hand in on paper on the due date, please either hand in on paper early, hand in on paper late (with the late penalty), or ask a friend to deliver the paper version. In other words, please plan your submission in advance if you are not going to be on campus on the due date. |

Last modified Monday, 17-Apr-2017 00:19:46 EDT