1
$\begingroup$

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?

$\endgroup$
  • 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 '15 at 14:25
2
$\begingroup$

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.

$\endgroup$

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.