# Why may the right hand sides in Chomsky Hierachy type 1 be larger?

I'm shaking my head because of this question, my Prof. didn't explain it. We have linear space limited automata and they have to satisfy for rules a -> b that |a| <= |b|.

Why?

I would have said, that it's stupid to allow being larger, because we are space limited and still have to produce all words of a language.

Thank you in advance, an answer would mean a lot to me.

• I am not sure this makes sense. In particular, note that an LBA may use space in $\mathcal{O}(n)$, that is up to a constant factor more than the input size $n$. – Raphael Oct 19 '10 at 17:30
• @Raphael, true, but if the grammar allowed length-decreasing productions then it might be possible that the only derivation of a string x from the start symbol S would have intermediate steps of length, say, $2^{|x|}$. If you artificially restrict the grammar so that intermediate steps must be $c|x|$ if x is the final derivation, then you can easily just make it into a CSG by compressing characters. – mikero Oct 19 '10 at 17:54
• I still think the direct relation between grammar form and automaton makes sense. Take a grammar with rules $S \rightarrow SS | a | \varepsilon$. It creates sentential forms of arbitrary length but $a^*$ is CFL and therefore CSL and can be parsed by an LBA, even a DEA. That is because the automaton has not to simulate the grammar, it can be more clever. – Raphael Oct 20 '10 at 6:58