Bissoy.com
Doctors Medicines MCQs Q&A

Which of the following problems is undecidable ?

Which of the following problems is undecidable ? Correct Answer Ambiguity problem for context free grammar

The correct answer is option 4:

EXPLANATION

Option 1: Decidable

Minimize both finite automata if both are the same having automata then both are equivalent and hence to determine if two finite automata are equivalent is decidable 

Option 2: Decidable

For the context-free language, we have a CYK algorithm for membership problem, so it is decidable

Option 3: Decidable

There is an algorithm for the finiteness problem

ALGORITHM:

Step1: delete states which are not reachable from the initial state and corresponding transitions.

Step 2: delete states and corresponding transitions which are not reachable to the final state.

Step 3: In remaining finite automata, if we find at least one loop and one final state then it is accepting infinite language.

so the finiteness problem is decidable

Option 4: Undecidable

Decidable there is no algorithm for finding ambiguity in grammar, so ambiguity is undecidable.

Related Questions

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:
Which one of the following problems is undecidable?
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
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) = ϕ?
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)?  
Which of the following are undecidable problems?
Which of the following is/are correct? AC network analyzer is used to solve Status i. Load flow problems ii. Short circuit problems iii. Stability problems
If there are 150 questions in a 3 hr examination. Among these questions 50 are type A problems, which requires twice as much as time be spent on the rest of the type B problems. How many minutes should be spent on type A problems ?
Sohana's mathematics test had 75 problems i.e. 10 arithmetic, 30 algebra and 35 geometry problems each carrying I mark She answered 70% of the arithmetic, 40% of the algebra and 60% of the geometry problems correctly. She did not pass the test as she got less than 60% marks. How many more questions she would have needed to answer correctly to earn a 60% passing grade?