Question

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

1. I and IV only
2. II and III only
3. II, III and IV only
4. III and IV only

Answer 1

Correct Answer - Option 4 : III and IV only

Decidable properties of Languages:

For decidable: D

For un-decidable: U

For grammar: G

	Membership Problem w ∈ L(R)	Emptiness L(G) = ϕ	Universality L(G) = ∑*	Equality	L(G)= Regular	L(G) = Finite
Regular Language	D	D	D	D	D	D
DCFL	D	D	D	D	D	D
CFL	D	D	UD	UD	UD	D
CSL	D	UD	UD	UD	UD	UD
Recursive language	D	UD	UD	UD	UD	UD
Recursive enumerable language	UD	UD	UD	UD	UD	UD

 

From the above table:

Membership property of regular grammar is decidable.

Emptiness problem of context free grammar is decidable.

Universality property for context free grammar is undecidable.

Membership problem of Turing machine is undecidable.