Question

Let Show that is decidable.

Short answer

$C_{CFG}$ is decidable.

Step-by-step solution

Define CFG

A context free grammar, or CFG, is a formal grammar that is used to construct any pattern of strings in a particular formal language. The tuples in a context free language are$\mathbf{:}\mathit{G}\mathbf{=}\left(V,T,P,S\right)$.

Show that CCFG is decidable

Consider a decider D that checks for the finiteness of the context-free language.

Consider another decider D₁that shows that a given language is decidable.

The decider D₁ can be defined as follows:

• On input ,G is the CFG and k is the string. Check the finiteness of the L(G) using the decider D.
• If $L\left(G\right)=\infty$and $k=\infty$, then it is accepted.
• If $L\left(G\right)=\infty$and $k\ne \infty$, then it is rejected.
• If L(G) is finite and $k=\infty$,then it is rejected.
• If L(G) is finite and $k\ne \infty$, continue.

Calculate the pumping lemma l for the grammar G and set the $count=0$. Use for loop to get the strings that has the length equal to i .Increment the $count$value if the string is generated by G. Accept if the value of count is equal to k, otherwise reject.

In the above decider definition, it has a finite number of steps, therefore, it can check easily.

Hence, D₁ is a decider that decides the language $C_{CFG}$ and is decidable, which has been proven.