4
$\begingroup$

I have been given the following problem and was wondering if my solution is correct: Say that a variable $A$ in CFG $G$ is necessary if it appears in every derivation of some string $w$ where $w$ is in $G$. Let $$\text{NECESSARY}_{\text{CFG}} =\{\langle G,A\rangle \mid G\text{ is a CFG and }A\text{ is a necessary variable in }G\}$$

  1. Show that $\text{NECESSARY}_{\text{CFG}}$ is Turing-recognizable.
  2. Show that $\text{NECESSARY}_{\text{CFG}}$ is undecidable.

This problem is a textbook exercise in the book Introduction to the Theory of Computation by Martin Sipser.


This is my solution to part 1.

$D$ = On input $\langle G,A\rangle$:

  1. Create a CFG $H$ by eliminating the $A$ variable from the derivations of $G$.
  2. Create list of strings $w$ generated by grammar $G$.
  3. Create a decider for $\text{A}_{\text{CFG}}$ and check if each string of $w$ can also be generated by $H$.
  4. If $w$ strings cannot be generated by $H$ then accept.
  5. If some string cannot be generated by $H$ then reject.

For part 2, I don't have a solution. My thoughts would be to somehow reduce this to $\text{ALL}_{\text{CFG}}$ which is known to be undecidable.

$\endgroup$

2 Answers 2

7
$\begingroup$

An approach for the undecidability

Let $G$ be a context-free grammar. We can add to $G$ new context-free generation rules that employs new variables without using any variables in $G$ (except the initial variable of $G$) so that we end up with a grammar $H$ such that $H\in\text{ALL}_{\text{CFG}}$ and

$\quad$ $G\in\text{ALL}_{\text{CFG}}$ $\iff$ every new variable is not necessary in $H$.

Were $\text{NECESSARY}_{\text{CFG}}$ decidable, we could decide the right-hand side, and hence the left-hand side as well.

Some minor issues of your solutions

Your solution to part 1 is basically correct.

There are, apparently, some typos in step 4 and step 5. Step 5 , "... then reject" might be wrong since this procedural cannot end with rejecting when $L(G)$ contains infinitely many strings. It is unnecessary any way.

Here is a better way to write your solution.

Turing machine $D :=$ On input $\langle G,A\rangle$:

  1. Create a CFG $H$ by eliminating variable $A$ from the generation rules of $G$.
  2. Create a decider for $\text{A}_{\text{CFG}}$.
  3. For each string $w$ in $\Sigma^*$:
    1. Use the decider to check whether $\langle G,w\rangle\in\text{A}_{\text{CFG}}$ and whether $\langle H,w\rangle\in\text{A}_{\text{CFG}}$. If the former is yes and the latter is no, accepts.

It is easy to see that $D$ recognizes $\text{NECESSARY}_{\text{CFG}}$. Note that there is no need to specify when or whether $D$ rejects.


You are on the right track on the undecidability.

Note that the right way is "to reduce $\text{ALL}_{\text{CFG}}$ to this" instead of "to reduce this to $\text{ALL}_{\text{CFG}}$".

The mental model is to view "$\text{ALL}_{\text{CFG}}$" as such a "huge and difficult" problem that it cannot be "reduced" to another small and easy problem. If we do find a reduction, the other problem must also be "huge and difficult", which is what we want.

$\endgroup$
1
  • $\begingroup$ Perfect, thank you so much! $\endgroup$
    – Stecco
    Apr 5 at 13:32
6
$\begingroup$

Let $G$ be a context-free grammar over an alphabet $\Sigma$ with initial variable $S$. Create a new grammar $G'$ with a new initial variable $S'$, a new variable $A$, and transitions $S' \to S \mid A$, $A \to \sigma A$ for every $\sigma \in \Sigma$, and $A \to \epsilon$. You take it from here.

$\endgroup$
1
  • $\begingroup$ Amazing, thank you!! $\endgroup$
    – Stecco
    Apr 5 at 13:31

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.