0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This question is impossible to answer for people not owning the textbook. Please copy the relevant parts from the textbook. $\endgroup$ – Yuval Filmus Jan 6 '17 at 19:42
  • $\begingroup$ Here is what book says. $\endgroup$ – Maha Jan 6 '17 at 20:00
  • $\begingroup$ This is not enough, since I don't know what Equation (5.2) is. Besides, you should edit all this information into the body of the question. $\endgroup$ – Yuval Filmus Jan 6 '17 at 20:02
  • $\begingroup$ Equation (5.2) is the one which I have included in the fact block quote in the body of question. I have also already added link to the google book page 143 in the question body which contains Theorem (5.2) and on page 144, you can find equation (5.2). $\endgroup$ – Maha Jan 6 '17 at 20:19
  • $\begingroup$ I cannot access the google book, nor should I have to. Everything needed to answer your question has to be part of your question. $\endgroup$ – Yuval Filmus Jan 6 '17 at 20:19
1
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.