Elimination of useless symbols in context-free grammar

Question

suppose we have a context-free grammar (CFG):

$v_0 → v_1v_1$

$v_1 → v_0v_0 | a$

$v_2 → v_1v_2 | b$

and we want to simplify it by:

• removing useless symbols (symbols that will never be in a word by the grammar)
• removing $Ɛ$-productions (such as $A → Ɛ$)
• removing unit productions (such as $A → B$).

We can see, that we won't be removing any $Ɛ$-productions, as there aren't any. There are also none unit productions, as every symbol generates two non-terminal symbols or a terminal symbol.

I am not sure about the useless symbols though. How can I check if this grammar can be further simplified and if there are any useless symbols to remove?

My guess is that since $v_0$ is not generating any terminal symbol, it can be removed, so we would have:

$v_1 → a$

$v_2 → v_1v_2 | b$

and now every symbol is reachable and generating. Is that true?

Answer 1

My guess is that since $v_0$ is not generating any terminal symbol, it can be removed…

But $v_0$ does generate terminal sentences, even if it doesn't do so in a single derivation step. Starting with $v_0$, we can derive:

$$v_0 \to v_1v_1 \to av_1 \to aa$$

But the grammar does not derive $a$, so your suggested replacement is not the same language.