Reducibility Problem

Question

Consider 2 problems X & Y. Now if X is reducible to Y.What does this mean.please explain with an example.

Comments

The following has been taken from Peter Linz

"We say that a problem A is reduced to a problem B if the
decidability of A follows from the decidability of B. Then, if we know that A is undecidable, we can
conclude that B is also undecidable"

Answer 1

X is reducible to Y-->

Example-

Problem X:

"Let L be a Regular Language And G be a Context free grammar. Then whether L is a subset of the language generated by G is decidable or not?"

Problem Y:

"Let G & G' be two context free grammars. Then whether Language generated by G i.e. L(G) is a subset of language generated by L(G')  is decidable or not?

 

Now here we can clearly see that X is reducible to Y, because if we are provided with a Regular language we can easily get equivalent CFG.

So just by converting Regular Language to equivalent Context free grammar we can reduce problem x to problem y.

And we all know that problem y described above is undecidable, that's why problem x is undecidable.

 

Hope this helped. You all are requested to comment if anything described above is conceptually incorrect.

Thank u!!