2 votes 2 votes Consider $L=L_1 \cap L_2$ where $L_1 = \{ 0^m 1^m 20^n 1^n \mid m,n \geq 0 \}$ $L_2 = \{0^m1^n2^k \mid m,n,k \geq 0 \}$ Then, the language $L$ is Recursively enumerable but not context free Regular Context free but not regular Not recursive Theory of Computation ugcnetcse-oct2020-paper2 theory-of-computation recursive-and-recursively-enumerable-languages + – go_editor asked Nov 20, 2020 recategorized Nov 27, 2020 by Krithiga2101 go_editor 2.2k views answer comment Share Follow See 1 comment See all 1 1 comment reply eshita1997 commented Dec 8, 2020 reply Follow Share Intersection of CFL and Regular language is Context-Free Language. But not Regular. So option C. 0 votes 0 votes Please log in or register to add a comment.
2 votes 2 votes L1 is CFL (comparison possible by single stack) and L2 is regular (DFA is there ) so by Theorem of regular intersection L=L1 ∩L2 must be CFL so option C Sanjay Sharma answered Nov 22, 2020 Sanjay Sharma comment Share Follow See all 4 Comments See all 4 4 Comments reply Vishal_kumar98 commented Nov 30, 2020 reply Follow Share Is the first Language DCFL, Sir ? 1 votes 1 votes Sanjay Sharma commented Nov 30, 2020 reply Follow Share yes it is dcfl as we know deterministically what to do on rreading input string 1 votes 1 votes rakesh22 commented May 25, 2021 reply Follow Share sir L2 is not regular .observe 2^k we can not draw finite automata for this. 0 votes 0 votes Sanjay Sharma commented May 28, 2021 reply Follow Share whats the problem with 2^k , k >=0 simply a loop over alphabet 2 0 votes 0 votes Please log in or register to add a comment.
2 votes 2 votes The language L1 $ \cap $ L2 is $ 0^{m} 1^{m} 2 $ which is not regular by pumping lemma. However you can easily create a CFL for this. $ S’ \rightarrow S 2 $ $S \rightarrow 0 S 1, \epsilon $ Hence the answer is C. Joey answered Dec 24, 2020 edited Oct 7, 2021 by Joey Joey comment Share Follow See 1 comment See all 1 1 comment reply raja11sep commented Aug 13, 2021 reply Follow Share Typo. It should be an intersection. 1 votes 1 votes Please log in or register to add a comment.