The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
7 views
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?
asked in Theory of Computation by Active (1.2k points)
edited by | 7 views
0
can u plz explain the problem here?i aint getting anything between r1 and r2
0
Sorry but the problem is given in this manner only.
0
from where did u got this question?
0
Peter Linz
0
page number?
0
Sorry it's my mistake now I have edited the question.
0
Page number 321 que. no.8 5th edition
0
i think answer should be C.
0
Can you please give the proof for that?
0
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.

Please log in or register to answer this question.



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

38,053 questions
45,545 answers
131,862 comments
48,884 users