In wikipedia there's the definition for "Proper CFG".

A context-free grammar is said to be proper, if it has

$$\text{no unreachable symbols}: \forall N \in V: \exists \alpha,\beta > \in (V\cup\Sigma)^*: S \stackrel{*}{\Rightarrow} \alpha{N}\beta$$ $$\text{no unproductive symbols}: \forall N \in V: \exists w \in > \Sigma^*: N \stackrel{*}{\Rightarrow} w$$ $$\text{no ε-productions}: > \neg\exists N \in V: (N, \varepsilon) \in R$$ $$\text{no cycles}: > \neg\exists N \in V: N \stackrel{+}{\Rightarrow} N$$


It's also stated that non-proper CFGs can be transformed into "weakly equivalent" CFGs:

In formal language theory, weak equivalence of two grammars means they generate the same set of strings, i.e. that the formal language they generate is the same.


but I cannot find the algorithm for doing this.

How is it done?

  • 1
    $\begingroup$ Please repeat the definitions here so a) readers don't have to search and guess what you mean and b) your question makes sense even after Wikipedia changes. $\endgroup$
    – Raphael
    Dec 29, 2015 at 14:25

1 Answer 1


First of all, Wikipedia does supply a reference to a standard textbook. Second, since a proper grammar is one without unproductive symbols, to make a grammar proper all you have to do is erase all unproductive symbols and all productions involving them.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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