December2015 cs Q23

0. 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

Your email address will not be published. Required fields are marked *


Cancel reply

Your email address will not be published. Required fields are marked *