2
$\begingroup$

Consider the following language

$L$ = {$<G><w>$ | $G$ is a CFG and $w\in L(G)$}

Now, I wish to prove that $L$ is Turing decidable. My gut tells me to construct a Turing machine that simulates a NPDA that decide whether $w$ is indeed in $L(G)$. The TM will hold two tapes: one for the input and another to simulate the stack.

Am I in the right direction here?

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ There are many algorithms that decide whether $w \in L(G)$ for context-free $G$. See for example Wikipedia. $\endgroup$ – Yuval Filmus Jan 13 at 17:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.