Which of following problems are undecidable? I. Membership probl

Which of following problems are undecidable? I. Membership probl
|

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

A. I and IV

B. II and IV

C. III and IV

D. I and II

Please scroll down to see the correct answer and solution guide.

Right Answer is: B

SOLUTION

Concept

A problem is said to be Decidable if we can always construct a corresponding algorithm that can answer the problem correctly. Based upon this property, problems are classified as

  1. Decidable
  2. Semi-decidable
  3. Undecidable

Explanation:

Statement i: Decidable

Membership problem in CFL is decidable using CYK algorithm to check the membership.

Statement ii: Undecidable

To check whether a given CFL is regular or not in undecidable.

Statement iii: Decidable

To determine whether an FA halts on all inputs or not is decidable because we have final and non-final states in FAs that indicate whether the input string is accepted or not.

Statement iv: Undecidable

Membership problem for type 0 (Recursively Enumerable) grammars is undecidable.

Related Questions