Decidability

Question

Which of the following decision problem is undecidable?

I)Given a CFG $G=\left ( N,\Sigma ,P,S \right )$ and a string $x\epsilon \Sigma ^{*}$, does $x\epsilon L\left ( G \right )$?

II) Given CFG $G_{1},G_{2}$, Is $L\left ( G_{1} \right )=L\left (G_{2} \right )$?

Comments

yes membership only not support by REC and RE , rt?

but is there any logic why CFL support membership?

---

membership is Decidable upto REC.

it's because a PDA will always halt.

a Pda is nothing but an NFA with a stack.

---

membership problem is decidable for CFL because there exist an algorithm for it, which is CYK algorithm.

also whether the string is present in the language or not, the PDA always halts.

Answer 1

1) first one is membership problem of CFG.which is decidable.

2) second one is equvalence problem of  CFG . which is undecidable.