  A regular language is $k$-piecewise testable if it is a finite boolean
combination of languages of the form $\Sigma^* a_1 \Sigma^* \cdots \Sigma^* a_n
\Sigma^*$, where $a_i\in\Sigma$ and $0\le n \le k$. Given a DFA $A$ and $k\ge
0$, it is an NL-complete problem to decide whether the language $L(A)$ is
piecewise testable and, for $k\ge 4$, it is coNP-complete to decide whether the
language $L(A)$ is $k$-piecewise testable. It is known that the depth of the
minimal DFA serves as an upper bound on $k$. Namely, if $L(A)$ is piecewise
testable, then it is $k$-piecewise testable for $k$ equal to the depth of $A$.
In this paper, we show that some form of nondeterminism does not violate this
upper bound result. Specifically, we define a class of NFAs, called ptNFAs,
that recognize piecewise testable languages and show that the depth of a ptNFA
provides an (up to exponentially better) upper bound on $k$ than the minimal
DFA. We provide an application of our result, discuss the relationship between
$k$-piecewise testability and the depth of NFAs, and study the complexity of
$k$-piecewise testability for ptNFAs.
