Month 8: Theory of Computation

Quiz 01 Solutions - Mike Allen

- 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.
`[0+(0+1)(1+00)*01]*(0+1)(1+00)*` - Write a linear grammar where each right side is of the form aB or a.
`A -> 0A | 0B | 1B`

B -> 1B | 0C | e

C -> 0B | 1A

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

**answer:**

- 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.
**REGULAR**. This language can be accepted by the following NFA: - The set 1
^{m}0^{n}1^{m+n}, for m and n greater than or equal to one.**NOT REGULAR**by the pumping lemma. Let p be the pumping length and consider the string s=1^{p}0^{p}1^{2p}. Now we try to break it up into s=xyz. Since |xy|<=p and |y|>0, y can only contain 1s. When we pump the string once we get xy^{2}z = 1^{p+|y|}0^{p}1^{2p}which is not in the language. This contradicts the pumping lemma, so the language is not regular. - 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.
**REGULAR**. This language can be accepted by the following NFA:

- The set of all strings in which every third symbol is the same as the first symbol in the string.
- 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.
**CLOSED**Even(L) is just the intersection of L with a DFA which accepts strings of even length. Since L and this DFA are both regular, and regular sets are closed under intersection, regular sets must also be closed under Even. - Triple(L) = {x | x=uvw, such that u, v, w are in L, and |u| = |v| = |w|}.
**NOT CLOSED**by counterexample. Consider the language A = 0*1. Triple(A) has the form 0^{n}10^{n}10^{n}1 where n>=0. If we assume pumping length p and try to pump the string s=0^{p}10^{p}10^{p}1 which is in this language, we get s=0^{p+|y|}10^{p}10^{p}1 which is not. Since A is regular and Triple(A) is not, the set of regular languages is not closed under Triple.

- Even(L) is the set of all strings x in L such that |x| is even.
- 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)]*.

- Obtain a DFA for L1
- Obtain a DFA for the regular expression [00 + 11 + (01 + 10)(00 + 11)*(01 + 10)]*
- Intersect the two DFAs.
- If the result accepts anything, accept; Otherwise reject.