Question

Say that a variable $\mathbf{A}$ in CFLrole="math" localid="1659808454707" $\mathbf{G}$ is usable if it appears in some derivation of some string$\mathbf{w}\in \mathbf{G}$ . Given a CFG$\mathbf{G}$ and a variable $\mathbf{A}$, consider the problem of testing whether$\mathbf{A}$ is usable. Formulate this problem as a language and show that it is decidable.

Short answer

This problem or the statement given in the question 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.

Step 2:

A variable$A$in Context free language$\mathrm{G}$is usable if it appears in some derivation of some string $\mathrm{w}\in \mathrm{G}$. And a Context free grammar$\mathrm{G}$and a variable $\mathrm{A}$,

The given grammar isambiguous context free grammar because the language and the string are formed bythe given context free grammar there exist more than one left most derivation or more than one right most derivation or more than one parse tree is called ambiguous grammar.

$\begin{array}{l}\mathrm{S}\to \mathrm{SS}|\mathrm{T}\\ \mathrm{T}\to \mathrm{aTb}|\mathrm{ab}\end{array}$

The LHS derivation of the given grammar,

$\begin{array}{l}\mathrm{S}\to \mathrm{SS}|\mathrm{T}\\ \begin{array}{l}\mathrm{S}\to \mathrm{SS}\\ \mathrm{S}\to \mathrm{TS}\\ \mathrm{S}\to \mathrm{aTbS}\\ \end{array}\end{array}$

$\begin{array}{l}\mathrm{S}\to \mathrm{aTbS}\\ \mathrm{S}\to \mathrm{aabbS}\\ \mathrm{S}\to \mathrm{aabbT}\\ \mathrm{S}\to \mathrm{aabbab}\end{array}$

The RHS derivation of the given grammar,

$\begin{array}{l}\mathrm{S}\to \mathrm{SS}|\mathrm{T}\\ \begin{array}{l}\mathrm{S}\to \mathrm{SS}\\ \mathrm{S}\to \mathrm{ST}\\ \mathrm{S}\to \mathrm{Sab}\\ \end{array}\end{array}$

$\begin{array}{l}\mathrm{S}\to \mathrm{Sab}\\ \mathrm{S}\to \mathrm{Tab}\\ \mathrm{S}\to \mathrm{aTbab}\\ \mathrm{S}\to \mathrm{aabbab}\end{array}$

From both the derivation from LHS or RHS the derivation evaluated is same hence, this grammar is ambiguous context free grammar.

Hence, this grammar of context free grammar is usable and this problem is decidable.