Consider now the family of context-sensitive languages. Exhaustive search
parsing is possible here also since only a limited number of productions are
applicable at each step. Following the analysis leading to Equation (5.2), we see
that the maximum number of sentential forms is
.
Note, however, that we cannot claim from this that
because we cannot put an upper bound on |P| and c.
From these examples we note a trend: As T (n) increases, more and more of
the families L REG , L CF , L CS are covered. But the connection between the
Chomsky hierarchy and the complexity classes is tenuous and not very clear.
EXERCISES
1. Complete the argument in Example 14.4.
2. Show that L = {ww R w : w ε {a, b} + } is in DTIME (n).
3. Show that L = {www : w ε {a, b} + } is in DTIME (n).
4. Show that there are languages that are not in NTIME (2 n ).
14.4 The Complexity Classes P and NP
At this point, it is instructive to summarize the difficulties we have encountered
in trying to find useful complexity classes for formal languages and draw a few
conclusions.
1. There exists an infinite number of properly nested complexity classes DTIME
(n k ),k = 1, 2,…. These complexity classes have little connection to the
familiar Chomsky hierarchy and it seems difficult to get any insight into the
nature of these classes. Perhaps this is not a good way of classifying
languages.
parsing is possible here also since only a limited number of productions are
applicable at each step. Following the analysis leading to Equation (5.2), we see
that the maximum number of sentential forms is
.
Note, however, that we cannot claim from this that
because we cannot put an upper bound on |P| and c.
From these examples we note a trend: As T (n) increases, more and more of
the families L REG , L CF , L CS are covered. But the connection between the
Chomsky hierarchy and the complexity classes is tenuous and not very clear.
EXERCISES
1. Complete the argument in Example 14.4.
2. Show that L = {ww R w : w ε {a, b} + } is in DTIME (n).
3. Show that L = {www : w ε {a, b} + } is in DTIME (n).
4. Show that there are languages that are not in NTIME (2 n ).
14.4 The Complexity Classes P and NP
At this point, it is instructive to summarize the difficulties we have encountered
in trying to find useful complexity classes for formal languages and draw a few
conclusions.
1. There exists an infinite number of properly nested complexity classes DTIME
(n k ),k = 1, 2,…. These complexity classes have little connection to the
familiar Chomsky hierarchy and it seems difficult to get any insight into the
nature of these classes. Perhaps this is not a good way of classifying
languages.