Month 8: Theory of Computation

Quiz 01 - Prof. Shai Simonson

- Finite State Machines. (15 points)
Consider the following NFA over the alphabet {0,1}:

- Convert this NFA to a minimal DFA.
- Write a regular expression for the set the machine accepts.
- 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.

- More Machines. (5 points)
Draw a finite state machine that accepts the complement of the language accepted by the non-deterministic machine below:

- Regular or Not, Here I Come. (15 points)
Determine and prove for each set below whether it is Regular or not. Be careful.

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

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

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

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