CPS420

W2017 Assignment 3

Ryerson University

Worth: 10%

Finite State Automata, Regular Expressions, and Counting

Due: Tuesday April 18


Team Size

This lab can be done in teams of 1 or 2.

Assignment Description

Part A - Automata Construction

  1. 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.)
  2. 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)
  3. 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)
  4. Assuming that you have the following three automata, A1, A2, A3 recognizing the languages L1, L2, L3 respectively, shown here as black boxes:
    1. Draw an NFA called A which recognizes the language L1 (L2 | L3)
    2. What is the starting state of A?
    3. What are A's final states?

Part B - Recognizing Automata

  1. Give a precise, concise, and unambiguous English description of the language accepted by this automaton:
  2. Give a regular expression describing the language accepted by this automaton:
  3. Give a regular expression describing the language accepted by this automaton:

Part C - Counting

16 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.
In the following questions, you are asked to count the possible outcomes on the podium. These are the outcomes of the finals, which results in three medals: gold, silver, and bronze. You can abbreviate these medals as "G", "S", and "B" in your explanations.
  1. How many possible outcomes will there eventually be on the podium (by individual swimmer)?
  2. 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.
  3. Based solely on the number of athletes per country in the semi-finals and not on their relative swimming abilities:
    1. What is the probability that Canada will earn at least one medal?
    2. What is the probability that Hungary will earn at least one medal?
    3. What is the probability that Japan will earn at least one medal?

References

Hand In

This 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.
  • Hand in your written solution with a marking sheet (docx or pdf) stapled to the front.
  • In addition to the assignment itself you will need to also submit the Assignment 3 Submission Declaration on D2L. This assignment will not be graded unless this declaration has been submitted.


This page is maintained by Sophie Quigley (cps420@scs.ryerson.ca)
Last modified Monday, 17-Apr-2017 00:19:46 EDT