0 votes 0 votes Let G1 and G2 be grammars with G1 regular.Is the problem L(G1)=L(G2) decidable when a)G2 is unrestricted, b)when G2 is context free, c)when G2 is regular? saumya mishra asked Aug 10, 2018 • edited Aug 10, 2018 by saumya mishra saumya mishra 926 views answer comment Share Follow See all 10 Comments See all 10 10 Comments reply Show 7 previous comments arvin commented Aug 10, 2018 reply Follow Share i think answer should be C. 0 votes 0 votes saumya mishra commented Aug 10, 2018 reply Follow Share Can you please give the proof for that? 0 votes 0 votes arvin commented Aug 10, 2018 reply Follow Share to make it more simple i have reduced it to (intersection+regularity). i mean L(G1) (INTERSECTION) L(G2) == REGULAR to be decidable. and for first two case there is ambiguity for the L(G2) to be regular or not. so they both are Undecidable as regular interstion other languages may or maynot be regular. 0 votes 0 votes Please log in or register to add a comment.