5
$\begingroup$

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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
4
$\begingroup$

It is not allowed to be larger, it has to be larger! If you allow the right side being shorter, you have context sensitive deleting grammars which have the same power as unrestricted grammars, thus leaving the realms of CSL.

The space limitation you mention relates to the automaton concept that is equivalent to context sensitive grammars, not the grammars itself.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I see, thank you. The slides we were provided didn't explain that. $\endgroup$
    – leto
    Oct 10, 2010 at 18:27
4
$\begingroup$

I think the confusion is that the grammar is generative, while the automaton is not. The automaton is given a string and must decide whether the string is a possible outcome of applying the production rules. So think of the automaton as working backwards trying to trace back these productions in reverse to see if the start symbol S is ever reachable. Since the automaton only has linear space, we can't allow the intermediate string to grow larger than the original input. Reversing a production must not increase the size of the string, so applying a production in the forward direction cannot decrease the size of the string.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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$. $\endgroup$
    – Raphael
    Oct 19, 2010 at 17:30
  • 2
    $\begingroup$ @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. $\endgroup$
    – mikero
    Oct 19, 2010 at 17:54
  • $\begingroup$ 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. $\endgroup$
    – Raphael
    Oct 20, 2010 at 6:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.