MCQ IN COMPUTER SCIENCE & ENGINEERING

COMPUTER SCIENCE AND ENGINEERING

THEORY OF COMPUTATION

Please wait while the activity loads.
If this activity does not load, try refreshing your browser. Also, this page requires javascript. Please visit using a browser with javascript enabled.

If loading fails, click here to try again

Question [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]

Which of the following problems is undecidable?

A	Membership problem for CFGs
B	Ambiguity problem for CFGs
C	Finiteness problem for FSAs
D	Equivalence problem for FSAs

Explanation:

Detailed explanation-1: -Problem mentioned in option (2) Ambiguity problem for context-free grammar (CFGS) is undecidable. The ambiguity of grammar is undecidable, i.e there is no particular algorithm for removing the ambiguity of grammar.

Detailed explanation-2: -Only ambiguity problem for CFGs are undecidable.

Detailed explanation-3: -Which of the following problems is undecidable? Ambiguity problem for context free grammar is undecidable. So, option (D) is correct.

Detailed explanation-4: -Decidable there is no algorithm for finding ambiguity in grammar, so ambiguity is undecidable.

Detailed explanation-5: -Deciding if a given context-free grammar is ambiguous. Deciding if a given string is generated by a given context-free grammar.

There is 1 question to complete.