Editing Chomsky normal form (section)

===Order of transformations===

{| class="wikitable collapsible" style="float:right"
|-
|+ Mutual preservation<BR>of transformation results
|-
| colspan=6 | Transformation ''X'' {{color|#004000|always preserves}} ({{Aye}})<BR>resp. {{color|#400000|may destroy}} ({{Nay}}) the result of ''Y'':
|-
! {{diagonal split header|''X''|''Y''}}
! START  ||TERM||BIN||DEL||UNIT
|-
! START 
|        || {{Ya}}   || {{Ya}}  || {{Na}}  || {{Na}} 
|-
! TERM 
| {{Ya}} ||          || {{Na}}  || {{Ya}}  || {{Ya}} 
|-
! BIN 
| {{Ya}} || {{Ya}}   ||         || {{Ya}}  || {{Ya}} 
|-
! DEL 
| {{Ya}} || {{Ya}}   || {{Ya}}  ||         || {{Na}} 
|-
! UNIT 
| {{Ya}} || {{Ya}}   || {{Ya}}  ||{{Ya|text=({{Aye}})<sup>*</sup>}}||  
|-
| colspan=6 | <sup>*</sup>'''UNIT''' preserves the result of '''DEL'''<BR>&nbsp; if '''START''' had been called before.
|}

When choosing the order in which the above transformations are to be applied, it has to be considered that some transformations may destroy the result achieved by other ones. For example, '''START''' will re-introduce a unit rule if it is applied after '''UNIT'''. The table shows which orderings are admitted.

Moreover, the worst-case bloat in grammar size<ref group=note>i.e. written length, measured in symbols</ref> depends on the transformation order. Using |''G''| to denote the size of the original grammar ''G'', the size blow-up in the worst case may range from |''G''|<sup>2</sup> to 2<sup>2 |G|</sup>, depending on the transformation algorithm used.<ref name="Lange.Leis.2009"/>{{rp|7}} The blow-up in grammar size depends on the order between '''DEL''' and '''BIN'''. It may be exponential when '''DEL''' is done first, but is linear otherwise. '''UNIT''' can incur a quadratic blow-up in the size of the grammar.<ref name="Lange.Leis.2009"/>{{rp|5}} The orderings '''START''','''TERM''','''BIN''','''DEL''','''UNIT''' and '''START''','''BIN''','''DEL''','''UNIT''','''TERM''' lead to the least (i.e. quadratic) blow-up.