Question

Given an arbitrary context free grammar G, we define L as below.
L=(0+1)* if G is ambiguous
And
L=j if G is not ambiguous
Which of the following is true?
a. L is a context-free language
b. L is recursive but not r.e.
c. What L is depends on whether we can determine if G is ambiguous or not
d. What L is is undecidable

Answer 1

Answer on Question#38614 – Math - Other

We know the Post Correspondence Problem that determining whether or not an arbitrary context-free language is ambiguous is undecidable.

So the correct answer is **d**.