MCQ: (A) In what follows, you may assume that G and H are context-free grammars

Question

MCQ:

(A) In what follows, you may assume that G and H are context-free grammars with terminal alphabet {0,1}, and R is a regular expression using symbols 0 and 1 only. You may assume that the problem "Is L(G) = (0+1)*?", that is, the problem of recognizing all and only the codes for CFG's G whose language is all strings of 0's and 1's, is undecidable.

You should try to determine which of the following problems are decidable, and which are undecidable:

Is Comp(L(G)) equal to (0+1)*? [Comp(L) is the complement of language L with respect to the alphabet {0,1}.]

Is Comp(L(G)) empty?

Is L(G) intersect L(H) equal to (0+1)*?

Is L(G) union L(H) equal to (0+1)*?

Is L(G) finite?

Is L(G) contained in L(H)?

Is L(G) = L(H)?

Is L(G) = L(R)?

Is L(G) contained in L(R)?

Is L(R) contained in L(G)?

Then, identify the true statement from the list below:

"Is L(G) finite?" is decidable.

--

(B)

Then, identify the true statement from the list below:

Explanation / Answer

Answer:-

(A) d is the answer.

That is, "is L (G) finite?" Is decidable.

(B) b is the answer.

Related Questions

Navigate

• Browse (All)
• Browse M
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.