CS 390 Solutions to Unit 18 Exercises

p. 195

5.23 (a)
5.20(a): Let n be the number of states of DFA that accepts L. Consider the string x = 0ⁿ10²ⁿ.

Suppose that x is written as x = uvw, |v| > 0, |uv|

n.
There are three possibilities for v: v = 0^k from the first part of x for some k, v = 0^k1 for some k including 0, and v = 0^k from the lasrt part of x for some k.

If v = 0^k from either part of x, then uv²w is not in L since it is not in the form 0ⁿ10²ⁿ.
If v = 0^k1 for some k including 0, then uv²w has two 1's. Hence it is not in L.
Hence by Pumping Lemma, L is not regular.

5.20(c): Let n be the number of states of DFA that accepts L. Consider the string x = 0ⁿ1²ⁿ.

Suppose that x is written as x = uvw, |v| > 0, |uv|

n.
There are three possibilities for v: v = 0^k for some k, v = 0^k1^m for some k and m, and v = 1^k for some k.

If v = 0^k for some k, then repeat v t times so that tk > 2n. Then uv^tkw = 0^p+tk+q1²ⁿ, where u = 0^p, w = 0^q1²ⁿ and n = p + k + q. Hence p +tk + q > 2n. Hence 0^p+tk+q1²ⁿ is not in L.
If v = 0^k1^m for some k and m, then v² = 0^k1^m0^k1^m. Hence uv²w can not be in in L.
Finally, if v = 1^k for some k, then uv²w = 0ⁿ1^p1^2k1^q, where u = 0ⁿ1^p, w = 1^q and 2n = p + k + q. Hence p + 2k + q > 2n. Hence uv²w is not in the language L.

Thus by Pumping Lemma, L is not regular.