December2015 cs Q23
| List I | List 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.
