# How to convert improper CFG to weakly equivalent one?

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$$

https://en.wikipedia.org/wiki/Context-free_grammar#Proper_CFGs

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.

https://en.wikipedia.org/wiki/Equivalence_(formal_languages)

but I cannot find the algorithm for doing this.

How is it done?

• 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.
– Raphael
Dec 29, 2015 at 14:25