Question

Let $\mathbf{\sum }\mathbf{=}\left\{0,1\right\}$.Show that the problem of determining whether a CFG generates some string in ${\mathbf{1}}^{\mathbf{*}}$is decidable. In other words, show that

is a decidable language.

Short answer

The given language is a decidable language.

Step-by-step solution

Decidable language

In terms of finite automata (FA), a decidable refers to a problem of testing whether a deterministic finite automata (DFA) accepts an input string. A decidable language corresponds to algorithmically solvable decision problems.

Explanation

Consider that $C$is a context-free language and R is a regular language, then $C\cap R$is context free. Therefore, $1*\cap L\left(G\right)$1 ∗ ∩ L(G) is context free. The following TM decides the language of this problem.

“On input :

1. Construct CFG H such that $L\left(H\right)=1*\cap L\left(G\right)$.

2. Test whether $L\left(H\right)=\varnothing$using the $E_{CFG}$decider R from the Theorem 4.8.

3. If R accepts, reject; if R rejects, accept.”

Therefore, the given language is decidable and it has been proven above.