Language & grammar – Theory of Computing

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.

error: Content is protected !!