Which one of the following is TRUE?

Answer: The correct statement is that the language of strings over {a,b} whose number of b’s is 3k+1 is regular.

• The language {a^n b^n | n ≥ 0} is not regular. Reason: use the pumping lemma. Choose s = a^p b^p; any pumping segment within the first p letters consists of a’s only, so pumping changes the number of a’s but not b’s, producing a string not in the language.

• The language {a^n | n is prime} is not regular. Reason: use the pumping lemma. Pick a prime q > p and s = a^q. Any y consists of a^t with t>0; pumping with i = q+1 yields length q(1+t), which is composite, so the pumped string is not in the language.

• The language of strings over {a,b} having a number of b’s equal to 3k+1 is regular. Reason: construct a DFA with three states that records the count of b’s modulo 3. On input a stay in the current state; on input b move to the next state cyclically. Accept the state corresponding to remainder 1. This finite-state construction shows the language is regular.

• The language {ww | w ∈ {0,1}*} is not regular. Reason: use the pumping lemma. Let w = 0^p1 and s = ww = 0^p1 0^p1; any pumped substring within the first p symbols is zeros from the first half, so pumping breaks the exact duplication and yields a string not of the form ww.