Computer Sciences > Gate 2016 Set-1 > decidablility
Which of the following decision problems are undecidable?
I. Given NFAs N1 and N2, is L(N1)∩L(N2) = Φ?
II. Given a CFG G = (N,Σ,P,S) and a string x ∈ Σ*, does x ∈ L(G)?
III. Given CFGs G1 and G2, is L(G1) = L(G2)?
IV. Given a TM M, is L(M) = Φ?
I. Given NFAs N1 and N2, is L(N1)∩L(N2) = Φ?
II. Given a CFG G = (N,Σ,P,S) and a string x ∈ Σ*, does x ∈ L(G)?
III. Given CFGs G1 and G2, is L(G1) = L(G2)?
IV. Given a TM M, is L(M) = Φ?
Correct : decidablility
Total Unique Visitors
Loading......