A R S D I G I T A   V N I V E R S I T Y
Month 8: Theory of Computation
Quiz 01 - Prof. Shai Simonson
  1. Finite State Machines. (15 points)

    Consider the following NFA over the alphabet {0,1}:

    1. Convert this NFA to a minimal DFA.
    2. Write a regular expression for the set the machine accepts.
    3. Write a linear grammar where each right side is of the form aB or a.
      (a a terminal and B a non-terminal) to generate the set.

  2. More Machines. (5 points)

    Draw a finite state machine that accepts the complement of the language accepted by the non-deterministic machine below:

  3. Regular or Not, Here I Come. (15 points)

    Determine and prove for each set below whether it is Regular or not. Be careful.

    1. The set of all strings in which every third symbol is the same as the first symbol in the string.
    2. The set 1m0n1m+n, for m and n greater than or equal to one.
    3. The set of strings where each string has an equal number of 0s and 1s, and every prefix of the string has at most one more 0 than 1, and at most one more 1 than 0.

  4. Closure. (10 points)

    Determine whether Regular sets are closed under each of the operations below. Prove your answers by an explanation and/or example or counterexample.

    1. Even(L) is the set of all strings x in L such that |x| is even.
    2. Triple(L) = {x | x=uvw, such that u, v, w are in L, and |u| = |v| = |w|}.

  5. Decision Algorithms. (5 points)

    Give a decision algorithm to determine whether a regular language L1 has one or more strings in common with the language described by the regular expression [00 + 11 + (01 + 10)(00 + 11)*(01 + 10)]*.