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.

   [0+(0+1)(1+00)*01]*(0+1)(1+00)*

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

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

answer:

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.

   REGULAR. This language can be accepted by the following NFA:
   

2. The set 1^m0ⁿ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^p0^p1^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²z = 1^p+|y|0^p1^2p which is not in the language. This contradicts the pumping lemma, so the language is not regular.

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

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.

   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.

2. 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ⁿ10ⁿ10ⁿ1 where n>=0. If we assume pumping length p and try to pump the string s=0^p10^p10^p1 which is in this language, we get s=0^p+|y|10^p10^p1 which is not. Since A is regular and Triple(A) is not, the set of regular languages is not closed under Triple.

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

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