Complexity of Context Sensitive Languages

Question

I was reading above complexity classes from Formal Languages and Automata book by Peter Linz.

It gives following facts (in Theorem 5.2):

Consider we have a CFG without null or unit productions. For parsing a string w, if restrict ourselves to leftmost derivation, we can have no more than $|P|$ sentential forms after one round, no more than $|P|^2$ sentential forms after the second round, and so on. Parsing $w$ in CFG without null or unit productions cannot involve more than $2|w|$ rounds. Therefore, the total number of sentential forms cannot exceed $M=|P|+|P|^2+⋯+|P|^{2|w|} =O(P^{(2|w|+1)})$

Then (in Example 14.5, citing back above theorem) it says

However we cannot claim that $CSL \subseteq DTIME(|P|^{cn+1})$ because we cannot put an upper bound on $|P|$ and $c$

I dont understand why it is trying to use the fact about CFLs to find time complexity of CSLs. Is it because if CFLs does not follow that DTIME complexity, CSLs will also not follow it as $CFL\subset CSL$? But then, given any grammar, $|P|$ is fixed, its not infinite and I feel $c$ is always 2 as given in the proof of the theorem 5.2.

Answer 1

When the book says

Following the analysis leading to Equation (5.2),

it implies that if you apply the same kind of reasoning that resulted in Equation (5.2) to context-sensitive languages, then you will get the similar equation

$$ N = |P| + |P|^2 + \ldots |P|^{cn} = O(|P|^{cn+1}). $$

This equation is the analog of Equation (5.2) for context-sensitive languages. To prove this equation, you use reasoning similar to that used to prove Equation (5.2).