Which of the following statement is correct?

1. AAckermann's function is primitive recursive.
2. BL = {aⁿbᵏcⁿ⁺ᵏ : n ≥ 0, k ≥ 0} is a regular language.
3. CL = {aⁿbʲ : n = j²} is not a context-free language.
4. DFor every context-sensitive language L not including λ, there exists some linear bounded automaton M such that L ≠ L(M).

Pick an option to check yourself, or open the answer below.

Show answer & explanation

Correct answer: C. L = {aⁿbʲ : n = j²} is not a context-free language.

Explanation

Ackermann's function is total recursive but not primitive recursive. aⁿbᵏcⁿ⁺ᵏ needs a stack, so it is context-free, not regular. {aⁿbʲ : n = j²} fails the CFL pumping lemma. Every CSL (without λ) is accepted by some LBA, so D is false.