  We show quantum lower bounds for two problems. First, we consider the problem
of determining if a sequence of parentheses is a properly balanced one (a Dyck
word), with a depth of at most $k$. It has been known that, for any $k$,
$\tilde{O}(\sqrt{n})$ queries suffice, with a $\tilde{O}$ term depending on
$k$. We prove a lower bound of $\Omega(c^k \sqrt{n})$, showing that the
complexity of this problem increases exponentially in $k$. This is interesting
as a representative example of star-free languages for which a surprising
$\tilde{O}(\sqrt{n})$ query quantum algorithm was recently constructed by
Aaronson et al.
  Second, we consider connectivity problems on directed/undirected grid in 2
dimensions, if some of the edges of the grid may be missing. By embedding the
"balanced parentheses" problem into the grid, we show a lower bound of
$\Omega(n^{1.5-\epsilon})$ for the directed 2D grid and
$\Omega(n^{2-\epsilon})$ for the undirected 2D grid. The directed problem is
interesting as a black-box model for a class of classical dynamic programming
strategies including the one that is usually used for the well-known edit
distance problem. We also show a generalization of this result to more than 2
dimensions.
