CS 390 Solutions to Unit 17 Exercises

pp. 194 - 195

5.20(c): To distinguish two strings   0^m   and   0ⁿ,   m n,   select a string   0ⁱ1^j   such that   i m - 2n   and   j = i + m.
Then   0^m0ⁱ1^j = 0^{i + m}1^j   is in L since   j = i + m.   However,   0ⁿ0ⁱ1^j = 0^{i + n}1^j   is not in L, because   j i + n   and   j (= i + m) 2(i + n)   either.

5.26(f): Not necessarily true. For example L₁ = {a, b}* is regular and L₂ = {aⁿbⁿ | n N }, where N is the set of natural numbers, is non-regular.
However, L₁ L₂ = L₁ is regular.

5.27(b): Let us consider the complement of the language. If a language can not contain any strings with substrings of the form ww, then aa or bb among others can not be substrings of its strings. The largest language whose strings do not contain substrings aa or bb is { , a, b, aba, bab }. Let us denote this language by W. Since W is regular, its complement is also regular. The language of this question is the complement of W. Hence it is regular.