Correct : Regular Grammar

The question asks which of the given languages is regular.
Analyze the Options:
A) L = { aⁿbⁿ | n ≥ 0 }: This language requires the number of a's to be equal to the number of b's. A finite automaton cannot keep track of equal numbers of a's and b's. Therefore, it is not regular.
Example: ab, aabb, aaabbb are in the language, but aab and abb are not.
B) L = { aⁿ | n is prime }: The language contains strings whose length is a prime number. A finite automaton cannot determine whether an arbitrarily large number is prime. Therefore, it is not regular.
Example: a², a³, a⁵ are in the language, but a⁴ and a⁶ are not.
C) L = { w | w has 3k+1 b's for some k ∈ N, with Σ = {a,b} }: The number of b's must be of the form 3k+1. A finite automaton can keep track of the number of b's modulo 3. Therefore, this language is regular.
Example: If k = 0, the string can have 1 b, such as "b" or "ab". If k = 1, it must have 4 b's, such as "bbbb" or "abbbba". If k = 2, it must have 7 b's. Hence, the language accepts strings with 1, 4, 7, 10, ... b's.
D) L = { ww | w ∈ Σ, with Σ = {0,1} }: This language contains strings formed by repeating the same string twice. A finite automaton cannot generally remember the first half and compare it with the second half. Therefore, it is not regular.
Example: 00, 0101, and 1010 are in the language, while 0010 and 0110 are not.
Correct Answer: C) The Language L = { w | w has 3k+1 b's for some k ∈ N with Σ = {a,b} } is regular.