CODEWITHSUNDEEP
context-free-grammar
Alex M.M.
Alex M.M.

Reputation: 501

Can a Context-free grammar exist, where all of its symbols are useless?

Let G be a context-free grammar, defined with terminals (a,b), starting at S, and having variables (A,B,C,D,E,F,G)

with these production rules:

S -> aA | BD
A -> aA | aAB | aD
B -> aB | aC | BF
C -> Bb | aAC | E
D -> bD | bC | b
E -> aB | bC
F -> aF | aG | a
G -> a | b

I tried to reduce first the non-generating symbols, removing A, B, C and E. Then after tracking the non-reachable symbols, I was left out with S -> nothing.

I have successfully dealt with tens of applications but this is the first case when my grammar self-implodes.

How can this be possible? Is there anything wrong I did? Are there any CFG with useless symbols only?

EDIT: I remind the algorithm's steps:
1) remove non-generating symbols (the generating X has one at least one derivation X -> w, where w is a string of terminals)
2) remove the non reachable symbols (X is reachable if S -> αXβ)

Upvotes: 2

Views: 695

Answers (1)

emi
emi

Reputation: 5410

The definition of a context-free grammar does not require its symbols to be reachable or productive, although every context-free grammar can be transformed into a weakly strongly equivalent (thanks, rici) grammar with no useless symbols. However, since the language of your grammar is nonempty, you probably applied the transformations incorrectly. For example, your grammar generates the string aab:

S ⇒ aA  (S → aA)
  ⇒ aaD (A → aD)
  ⇒ aab (D → b)

Upvotes: 3

Related Questions