Bissoy.com
Doctors Medicines MCQs Q&A

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) = ϕ?

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) = ϕ? Correct Answer III and IV only

I. Given NFAs N1 and N2, is L(N1) ∩ L(N2) = ϕ?

This is decidable, when we convert the NFA into DFA, if no common final state in it. Then this will become true.

II. Given a CFG G = (N, ∑, P, S) and a string x ∈ ∑*, does x ∈ L(G)?

Membership property of a context free grammar is decidable.

III. Given CFGs G1 and G2, is L(G1) = L(G2)?

Equivalence of two context free grammar is undecidable.

IV. Given a TM M, is L(M) = ϕ?   

Emptiness problem of Turing machine is undecidable.

Related Questions

Which of the following is/are undecidable? 1. G is a CFG. Is L(G) = Φ? 2. G is a CFG. Is L(G) = Σ*? 3. M is a Turing machine. Is L(M) regular? 4. A is a DFA and N is an NFA. Is L(A) = L(N)?
Let L(R) be the language represented by regular expression R. Let L(G) be the language generated by a context free grammar G. Let L(M) be the language accepted by a Turing machine M. Which of the following decision problems are undecidable? I. Given a regular expression R and a string w, is w ∈ L(R)? II. Given a context-free grammar G, is L(G) = ϕ? III. Given a context-free grammar G, is L(G) = ∑* for some alphabet ∑? IV. Given a Turing machine M and a string w, is w ∈ L(M)?  
How many objects will be created? String a = new String("Examveda"); String b = new String("Examveda"); String c = "Examveda"; String d = "Examveda";
Imagine, you are solving a classification problems with highly imbalanced class. The majority class is observed 99% of times in the training data. Your model has 99% accuracy after taking the predictions on test data. Which of the following is true in such a case?
1. Accuracy metric is not a good idea for imbalanced class problems.
2.Accuracy metric is a good idea for imbalanced class problems.
3.Precision and recall metrics are good for imbalanced class problems.
4.Precision and recall metrics aren't good for imbalanced class problems.
Let G1 and G2 be arbitrary context free languages and R an arbitrary regular language. Consider the following problems: (A) Is L(G1) = L(G2)? (B) Is L(G2) ≤ L(G1)? (C) Is L(G1) = R? Which of the problems are undecidable ? Choose the correct answer from the options given below:
Suppliers(Sid: integer, sname:string, city:string, street:string) Parts(pid:integer, pname:string, color:string) Catalog(sid:integer, pid:integer, cost:real) Consider the following relational query on the above database: SELECT S.sname FROM Suppliers S  WHERE S.sid NOT IN (SELECT C.sid FROM Catalog C WHERE C.pid NOT IN (SELECT P.pid FROM Parts P WHERE P.color < > ‘blue’)) Assume that relations corresponding to the above schema are not empty. Which of the following is the correct interpretation of the above query?
What is the output of the following JAVA program? class Test { public static void main (String [ ] args) { Test obj = new Test (); obj.start (); } void start () { String stra="do”; String strb = method (stra); System.out.print(“:” + stra + strb); } String method (String stra) { stra=stra+”good”; System.out.print (stra); return “good”; } }
LN2 এবং MN2 এর মধ্যে MN2 অধিক -i. গলনাঙ্কবিশিষ্ট ii. পানিতে দ্রবণীয় iii. সমযোজী নিচের কোনটি সঠিক?
Which of following problems are undecidable? I. Membership problem in context-free languages II. Whether a given context-free language is regular III. Whether a finite state automation halts on all inputs IV. Membership problem for type 0 languages
Two persons are pulling the ends of a string in such a way that the string is stretched horizontally. When a weight of 10kg is suspended in the middle of the string the string does not remain horizontal. Can the persons make it horizontal again by pulling it with a greater force?