1. NOT. (1.17b) {www | w is {a,b}*}

   Assume that the language is regular. Let p be the pumping length, and choose s to be the string 0^p10^p10^p1. Now we try to break it up into s=xyz. Since |xy| <= p and |y|>0, y can only contain 0's. When we pump the string even just once we get xy²z = 0^p+|y|10^p10^p1, and this is not of the form www, since |y| > 0. This contradicts the pumping lemma, so the language is not regular.

2. NOT. (1.23c) {0^m1ⁿ | m is not equal to n}

   We know that

   	{0n1n | n >= 0}  = {0m1n | m,n >= 0}^{0*1*}c,
   

   where we are using ^ to denote intersection and ^c to denote complement. The proof is by contradiction. If {0^m1ⁿ | m is not equal to n} really were regular then {0ⁿ1ⁿ | n >= 0} would also be regular because 0*1* is regular and because of the closure properties of regular sets. Therefore it can't be regular

   There is a direct way to prove it as well: If p is the pumping length and we take the string s = 0^p1^p+p!, then no matter what the decomposition s = xyz is the string xy^1+p!/|y|z will equal 0^p+p!1^p+p! which is not in the language.

3. NOT. (1.23a) {0^m1ⁿ0^m | m,n >= 0}

   Assume that the language is regular. Let p be the pumping length, and choose s to be the string 0^p10^p. Now we try to break it up into s=xyz. Since |xy| <= p, y can only have zeros in it. Now xy^jz = 0^{p+ (j-1) |y|}10^p, and since |y|>0 the number of 0's on the left and right sides of xy^jz will not be the same for any j>1 so xy^jz will not be in the language, contradicting the pumping lemma. Therefore {0^m1ⁿ0^m | m,n >= 0} is not regular

4. REGULAR. The set of strings that have an even number of double zeros in them.

   This can be decided by the DFA below.
   

5. REGULAR. The set of all strings of the form xwx^R where x and w are strings over the alphabet {0,1}.

   This description is somewhat misleading. Since w can represent any string and x can be 0 or 1, this is the same as all strings which begin and end with the same character. This is easily seen to be a regular language.

6. NOT. The set of all strings over the alphabet {0} whose length is n! for some n>0.

   Assume that the set is regular. Let p be the pumping length. Without loss of generality we can assume that p is at least 2. (We can always increase the pumping length. We only do this because some of our calculations don't work for p = 1) Then, according to the pumping lemma, we can break the string s=0^p! into s=xyz where y has positive length and |xy| <= p. Then s=xy²z = 0^p! + |y| must also be in the language, so p!+|y| must also be a factorial. But (p+1)!-p! = (p)p! > p >= |y| so it follows that p! + |y| < (p+1)!, and therefore p! + |y| is not a factorial. This is a contradiction so the language cannot be regular.

7. NOT. The set of strings over the alphabet {0} of the form 0ⁿ where n is not prime.

   To prove this language is not regular, we instead examine the complement because the set of regular languages is closed under complement. Assume that the set is regular. Let p be the pumping lenght of the language. Then, according to the pumping lemma, we break the string s=0^p into s=xyz where y has positive length. Then, s=xyⁱz = 0^{p + (i-1) |y|} must also be in the set for any i. In particular let i = p+1. Then xy^p+1z=0^p+p|y| must be in the set so p + p|y| = p(1 +|y|) must be prime. Thus we have a contradiction and the set cannot be regular.

The flaw in the proof is the following: if p is the pumping length of 0*1* and s = 0^p1^p is decomposed into xyz in the usual manner then s absolutely positively can be pumped since xy^jz is equal to 0^p+(j-1)|y|1^p which will still be in 0*1*.

The pumping lemma only states that if a language is regular, then it can be pumped. The converse, if a language can be pumped, then it is regular, is not necessarily true, so irregular languages may satisfy the pumping lemma's conditions without contradicting it. In this particular case of

{aⁱb^jc^k | i,j,k >= 0,if i=1 then j=k},

if s is any string in the given language then the decomposition s = xyz with x = the empty string, y = to the first character of s, z = the rest of s, will always work with the pumping lemma. The resulting xy^jz will always be in the language.

1. Contains all strings of the form 0*1*.

   Given a DFA, M, we can determine if it accepts all strings of the form 0*1* by taking its complement and intersecting it with the DFA which accepts 0*1*, and then minimizing the resulting DFA. If the result is the machine that accepts nothing, then accept M, otherwise reject M.

2. Is co-finite.

   Given a DFA, M, we can determine if it is cofinite by taking its complement and then checking to see whether the result has any cycles from which an accept state is reachable. If it does not, then accept M, otherwise reject M.

3. Has at least one string w that has 111 as a substring.

   Given a DFA, M, we can determine if it accepts at least one string of the form 111 by intersecting it with another DFA which accepts (0+1)*111(0+1)* and minimizing the resulting DFA. If the result accepts anything, then accept M, otherwise reject M.

1. A regular grammar to generate the set of strings that are evenly divisible by 5
   A₀ -> 0A₀ | 1A₁ | e
   A₁ -> 0A₂ | 1A₃
   A₂ -> 0A₄ | 1A₀
   A₃ -> 0A₁ | 1A₂
   A₄ -> 0A₃ | 1A₄

2. A finite automaton can be converted into a right-linear grammar as follows:
   
   1. Reverse all the arrows in the finite automaton.
   2. Create a start state with epsilon transistions pointing towards each of the old accept states.
   3. Change the old start state to be the accept state.
   4. Convert the automaton as you would to get a left-linear grammar, except that terminals are placed on the right side. (ie A->Ba instead of A->aB)

1. Since we know that left and right linear grammars describe only regular languages and the set of palindromes over the language {0,1} is not regular, neither grammar can describe a palindrome.

2. If we allow a mixed left-right linear grammar, we can describe the palindromes as follows:
   S -> 0A | 1B | 0 | 1| e
   A -> S0
   B -> S1

1. Languages of the form 0^mx+b are accepted by DFAs of the form below, so they must be regular.
   

2. Unions of machines from the set described by (a) are regular, though not of the form 0^mx+b.

3. Extra Credit: This is actually fairly simple using the DFA characterization of regular sets. Since there can only be one transiton from each state the DFA is completely specified by giving
   1. The number of states, n, in the machine.
   2. An n-bit number, f, which tells us whether each state is final or not.
   3. A periodicity number, m, which has some value 0 <= m <= n

   The DFA is constructed by making state 1 the initial state, setting the j-th state to accept if and only if the j-th bit of the number f is a 1, adding a transition on 0 from state j to state j+1 for 1<= j <= j-1 and finally if m is not zero, adding a transition from state n to state n-m+1. The language constructed from this DFA will finite if m=0, and otherwise will be eventually periodic, of period m.

   It pretty easy to see from the above description that, up to a finite set, every regular language over 0 is of the form

   (0^b_1 + 0^b_2 + ... + 0^b_k)(0^m)*,

   for some choice of m, where {b_1, b_2, ..., b_k} is some subset of {0,1,2,...,m-1}