MUN Computer Science 1002 - Lab 8

Automata and combinatorics

Review:

• Lectures 25-27.

Vocabulary

• Regular languages
• Deterministic and non-deterministic finite automata
• Rules of sum and product, size of Cartesian products
• Permutations, combinations, r-permutations

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.
   • A language of all strings over $\{a,b,c\}$ containing a substring "abc".
   • A language of all strings over $\{0,1\}$ having 1 as a second-to-last bit (e.g, 010 and 1011 are ok, but not 001).

   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} :

   • A language of all strings that contain a substring "00".
   • A language of all strings over $\{0, 1\}$ which end with 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.

   • A language of all strings that do not contain a substring 11 (hint: use "missing edges").
   • A language of all strings that have 1 in the second-to-last bit (e.g, 010 and 1011 are ok, but not 001).

   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).