Bissoy.com
Doctors Medicines MCQs Q&A

Which one of the following problems is undecidable?

Which one of the following problems is undecidable? Correct Answer Ambiguity problem for CFGs

Problem mentioned in option (2) Ambiguity problem for context-free grammar (CFGS) is undecidable.

Explanation:- 

The ambiguity of grammar is undecidable, i.e there is no particular algorithm for removing the ambiguity of grammar. Here are some examples of ambiguous grammar:

  • S → aS | Sa | €
  • E → E + E | E*E | id
  • A → AA | (A) | a

 

Additional InformationEquivalence problem for FSAS:- An automation is a machine that has a finite number of states. Any two automation is said to be equivalent if both accept exactly the same set of strings.

Finiteness problem for FSAS:- The finiteness problem is decidable for FSAs ( also for CFGS) as we just need to check for a loop DFA.

Membership problem for CFGS:- The membership problem for a set is the problem of deciding which of two possible elements is logically more likely to belong to that set. In other words, given two elements of which at least one is in the set, to distinguish the member from the non-member.

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 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?
Given below are four jumbled sentences.Select the option that gives their correct order.  A.that is, many media outlets have been accused either of being too conservative or of being too liberal.  B.Who owns a media outlet often determines things such as the types of social problems that outlet presents, how long that outlet airs those problems, and how dramatically that outlet presents those problems.  C.The American media is often biased towards one or the other end of the political spectrum;   D.Mass media may use propaganda as a means to promote or publicize a particular political cause or point of view, or to maintain the viewer's attention. 
Consider the following two statements about regular languages: S1: Every infinite regular language contains an undecidable language as a subset. S2: Every finite language is regular. Which one of the following choices is correct?
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