464 views
0 votes
0 votes

It is possible to define the term simplification precisely by introducing the concept of complexity of a grammar. This can be done in many ways; one of them is through the length of all the strings giving the production rules.

For example, we might use

                      $complexity(G)=$$\sum_{A\rightarrow V ∈ P}${$1+|v|$}

Show that the removal of useless productions always reduces the complexity in this sense. What can you say about the removal of $λ$-productions and unit-productions?

Please log in or register to answer this question.

Related questions