Question

Let $\mathbf{C}\mathbf{=}\mathbf{\left\{}\mathbf{\right\{}\mathbf{G}\mathbf{,}\mathbf{x}\mathbf{\left\}}\mathbf{\right|}\mathbf{G}\mathbf{}\mathbf{is}\mathbf{}\mathbf{a}\mathbf{}\mathbf{CFG}\mathbf{}\mathbf{x}\mathbf{}\mathbf{is}\mathbf{}\mathbf{a}\mathbf{}\mathbf{substring}\mathbf{}\mathbf{of}\mathbf{}\mathbf{some}\mathbf{}\mathbf{y}\mathbf{\in }\mathbf{L}\mathbf{\left(}\mathbf{G}\mathbf{\right)}\mathbf{\}}\mathbf{.}$ Show that$\mathbf{C}$ is decidable.

Short answer

The language$\mathrm{C}$ is decidable.

Step-by-step solution

Context free language.

Context free language is a grammar where its language or string that formed by context free grammar is supports pushdown deterministic automata.

The problem is decidable.

Let,$\mathrm{C}=\left\{\right\{\mathrm{G},\mathrm{x}\left\}\right|\mathrm{G}\mathrm{is}\mathrm{a}\mathrm{CFG}\mathrm{x}\mathrm{is}\mathrm{a}\mathrm{substring}\mathrm{of}\mathrm{some}\mathrm{y}\in \mathrm{L}\left(\mathrm{G}\right)\}.$

Showing that,$\mathrm{C}$is decidable.

Let’s the following Turing machine $\mathrm{M}$= On input hG, xi,

Where, $\left(\mathrm{G}\right)$ is a context free grammar.

(a) Let $\mathrm{R}$be the following RE .

$\mathrm{R}=\mathrm{\Sigma }\ast \mathrm{x\Sigma }\ast$

(b) Create the context free grammar $\mathrm{H}$such that,

$\mathrm{L}\left(\mathrm{H}\right)=\mathrm{L}\left(\mathrm{G}\right)\cap \mathrm{L}\left(\mathrm{R}\right)$

(c) Submit$\mathrm{G}$ to the decider for ${\mathrm{E}}_{\mathrm{CFG}}$.

(d) If it accepts, then reject.

(e) Else, accept.

$\mathrm{M}$is clearly a decider since it halts. Also, $\mathrm{M}$accepts$\{\mathrm{G},\mathrm{x}\}$ .

If f generates some string$\mathrm{\Sigma }\ast \mathrm{x\Sigma }\ast$ in that is some string with$\mathrm{x}$ as a substring.

Hence, the language$\mathrm{C}$ is decidable.