Language & grammar – Theory of Computing
| Question 1 UGC NET June-2020 Match List I with List II: LR: Regular languages, LCF: Context free language, LREC: Recursive language, LRE: Recursively enumerable language.  |
| A – A-II, B-III, C-I |
| B – A-III, B-I, C-II |
| C – A-I, B-II, C-III |
| D – A-II, B-I, C-III |
Show Answer With Best Explanation
Answer : C
| Question 2 UGC NET June-2020 Consider L=L1 ∩ L2 where L1 = {0m 1m 20n 1n | m,n ≥0} L2 = {0m 1n 2k | m,n,k ≥0} Then, the language L is |
| A – Recursively enumerable but not context free |
| B – Regular |
| C – Context free but not regular |
| D – Not recursive |
Show Answer With Best Explanation
Answer : C
Explanation:
L1 = {0m 1m 20n 1n | m,n ≥0}
L2 = {0m 1n 2k | m,n,k ≥0}
L = L1 ∩ L2 = 0m 1m 2 | m >= 0} it is clearly not regular, because regular language doesn’t have capacity to count (or store) anything. Here 0’s followed by equal number of 1’s & context free language have capacity to do this. It is context free language but not regular.