ON NORMAL FORM GRAMMARS AND THEIR SIZE
This research is partially supported by projects VEGA 1/0692/08 (A. Kelemenová), IGS 37/2009, GAČR 201/09/P075 (L. Ciencialová) and by research plan MSM 4781305903 (L. Cienciala).
In this paper normal forms for context-free grammars, namely position restricted grammars, are treated and their influence to the size of the description of languages are presented. We discuss and compare several types of position restricted grammars and minimal size of grammars, expressed by the number of rules, needed to generate a language. Several techniques for the transformation of given grammar to an equivalent grammar in required form are used to reach upper bounds of the possible increase of the size complexity of languages related to different types of the position restricted grammars.
