UGC NET COMPUTER SCIENCE SOLVED PAPERS 2014-16 - UGC NET Computer Science Paper 3 December 2015

22. The family of context sensitive languages is __________ under union and __________ under reversal.

  • Option : B
  • Explanation : The family of context-sensitive languages is not closed under union and not closed under reversal.
Cancel reply
Cancel reply

23. Match the following

List IList II
(a) {an bn | n > 0} is a deterministic context free language(i) but not recursive language
(b) The complement of {an bn an | n> 0} is a context free language(ii) but not context free language
(c) {an bn an} is  context sensitive language(iii) but can not be accepted by a deterministic push down automation
(d) L is a recursive language(iv) but not regular

Codes:

 (a)(b)(c)(d)
(1)(i)(ii)(iii)(iv)
(2)(i)(ii)(iv)(iii)
(3)(iv)(iii)(ii)(i)
(4)(iv)(iii)(i)(ii)

  • Option : D
  • Explanation :
  • {anbn | n > 0 } is a deterministic context free language but not regular language
  • The complement of {anbnan| n > 0 } is context free language but not accepted by deterministic pushdown automata
  • {anbnan} is a context sensitive language but not recursive language
  • L is a recursive language but not a context free language
  • So, option (D) is correct.
Cancel reply
Cancel reply