In: Computer Science
The first five questions give languages over {0, 1}. In each case decide whether the language is regular or not, and prove your answer is correct.
5. The set of strings in which the number of 0's is a perfect square.
The given language is not regular. Use the pumping lemma for regular langauges to prove this.
Let the pumping length be . Consider the word which is in L as the number of 0s is a perfect square. Now consider any breakup of the word . Then as w consists of only 0s, y must also consists of only 0s, hence where the bound on length of y come from the bound on the length of xy.
Now consider the pumped up word . Then as per the bounds for i, it gives that . Note that this automatically means . Now consider . This implies . Hence is between two consecutive perfect squares and doesn't equal either of them. This implies that it cannot be equal to any perfect square, proving that .
Therefore the language doesn't satisfy the pumpign lemma for regular langauge, hence it is not regular. Comment in case of any doubts.