Which of the following statement is correct?

Question

Question

This question was previously asked in

UGC NET Computer Science (Paper 2) 17 June 2023 Official Paper

Ackermann's function is primitive recursive.
L= {anbkcn+k : n ≥ 0, k ≥ 0} is regular language.
L = {anbj : n = J2} is not context free language
For every context sensitive language L not including λ, there exists some linear bounded automata M such that L ≠ L(M).

Answer 1

The correct answer is L = {anbj : n = J2} is not context free language

EXPLANATION:

Ackermann's function is not primitive recursive.
- The primitive recursive functions form a subset of the total recursive functions or effectively calculable functions; however, there are total recursive functions which are not primitive recursive, such as the Ackermann function.
The language L= {anbkcn+k : n ≥ 0, k ≥ 0} is not regular.
- Regular languages adhere to the pumping lemma, which this language would violate. Given language is a Context free language.
L = {anbj : n = J2} is not context free language
- This is the correct statement. The language L isn't context-free as it represents a language where the number of 'a's is equal to the square of the number of 'b's.
- A context-free language wouldn't be able to generate or parse this kind of language, as it would require more context (like specific knowledge of numerical relationships) than a simple context-free grammar can provide. Because PDA can't able to calculation.
For any context sensitive language L, excluding λ (the empty string), there exists a linear bounded automaton M that recognizes the language such that L ≠ L(M).
- This is because a context-sensitive language is defined as a language that can be recognized by a linear bounded automaton. As such, the fourth statement as it stands is incorrect.