Prove that the following languages are not regular.
1. { 1^k : k is a perfect square } over the unary alphabet {1}.
2. { 1^k : k is NOT a perfect square } over {1}. Try two approaches: (a) Using closure properties & PL. (2) Do not use closure properties, only PL.
https://math.stackexchange.com/questions/2475669/prove-that-l-1-1m-m-is-not-a-perfect-square-is-not-regular-using
3. { 0^2n 1^n : n >= 0}
4. Use (3) and closure properties to prove for { w : #(0,w) = 2 * #(1,w) }
L intersection 0*1*
5. Use (3) and closure properties to prove for { 0^i 1^j : i is not equal to 2j }
0*1* - L
6. { 0^k : k is a power of 2 } over {0}.
7. 7. Prove this: If L is an infinite language accepted by a DFA, then there are integers p and q such that q > 0 and for every i >= 0, L contains a string of length p+iq.
[Follows from pumping lemma. Take some string of length more than the number of states in the DFA. Let q = |y| and p=|x|=|z| based on the partition that PL guarantees.]