edited by
881 views
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?
edited by

Please log in or register to answer this question.

Related questions

0 votes
0 votes
0 answers
2
baofbuiafbi asked Nov 14, 2023
141 views
Is the following language decidable or not? If you deem it decidable, you need to give an algorithm and analyse its running time. If not decidable, you need to prove it. ...
0 votes
0 votes
0 answers
3
baofbuiafbi asked Nov 14, 2023
142 views
Prove L = {F | F is a boolean formula and F evaluates to true on every asignment" is decidable (include algorithm and running time in big o notation)
0 votes
0 votes
0 answers
4
Abhipsa Panda asked May 24, 2022
148 views
How is equality problem for DCFL decidable?