  We answer two open questions by (Gruber, Holzer, Kutrib, 2009) on the
state-complexity of representing sub- or superword closures of context-free
grammars (CFGs): (1) We prove a (tight) upper bound of $2^{\mathcal{O}(n)}$ on
the size of nondeterministic finite automata (NFAs) representing the subword
closure of a CFG of size $n$. (2) We present a family of CFGs for which the
minimal deterministic finite automata representing their subword closure
matches the upper-bound of $2^{2^{\mathcal{O}(n)}}$ following from (1).
Furthermore, we prove that the inequivalence problem for NFAs representing sub-
or superword-closed languages is only NP-complete as opposed to PSPACE-complete
for general NFAs. Finally, we extend our results into an approximation method
to attack inequivalence problems for CFGs.
