MUN Computer Science 1002 - Lab 8

Automata and combinatorics




Individual work

Solve each of the following exercises.

  1. How many elements are in a set
    1. consisting of pairs of T-shirts and jeans, where there are 5 choices for T-shirts and 3 choices for jeans?
    2. of possible different set menu dinners each containing an appetizer, a main dish and a dessert, where there are 3 choices of appetizers, 5 choices of a main dish and 2 choices of desserts?
  2. How many strings of four decimal digits {0,...,9} (such as 1503, 9999,...)
    1. have distinct digits?
    2. do not contain the same digit four times?
    3. begin with an odd digit?
    4. have exactly three digits that are 4?
  3. List all
    1. permutations of {a,b,c}
    2. 2-permutations of {a,b,c,d}
    3. 2-combinations of {a,b,c,d}
  4. How many permutations of letters ABCDEFGH contain
    1. the string CDE?
    2. both strings CAB and DE?
  5. How many ways are there
    1. to choose 3 out of 10 students for a committee?
    2. to choose 3 out of 10 students, provided at least one of them must be first-year, and half of the 10 students are first-year?
    3. to seat n students and n faculty members around a (round) table so that students and faculty alternate?

    Group exercises

    For this part of the lab, you will be working in groups of three. In the first part of the exercise, each of three people in the group picks one of the topics below, and solves the corresponding questions. Then, each of you will explain to two of your peers how you have solved these questions. Your explanation should be good enough that they can then solve similar questions on their own.

    Topic 1: Regular expressions

    Write a regular expression for each of the languages below.

    Topic 2: Deterministic finite automata

    Recall that a finite automaton is deterministic if from every state it has exactly one outgoing edge for each letter from the alphabet. Draw deterministic finite automata accepting the following languages over {0,1} :

    Topic 3: Non-deterministic finite automata

    Recall that in a non-determinisitc finite automata it is OK to have multiple edges from the same state labeled with the same label (this is interpreted as "or"), and some edges might be missing (this is interpreted as "stop and reject"). Draw non-deterministic automata for the following languages.

    Review after the group exercises

    Consider the language of all strings over {0,1} that either contain "00" or have a 0 in the second-to-last position.

    1. Write a regular expression for this language.
    2. Draw a 4-state non-deterministic automaton for this language (use both multiple and missing edges).
    3. Draw a deterministic automaton for this language (hint: start by writing a 4-state deterministic automaton for "has 0 in second-to-last position", and attach it to the automaton that detects a "00" string).