Worst-Case Complexity of Quantifiers in Thompson's Construction
The point of a finite automaton is that the number of possible states that it can be in is finite. Specifically, if a NFA has $n$ states, then at any point in the input string, you can be in at most $n$ states at the same time.
The first observation is that you can precompute $\epsilon$ transitions. Define $\mathbf{closure} : Q \rightarrow 2^Q$ to be a function that takes a state and returns the state which are reachable using zero or more $\epsilon$ transitions. Then from this, we can compute an &quot;extended&quot; transition function $\delta^{*} : Q \times \Sigma \rightarrow 2^Q$, which maps a state and an input symbol to the set of states that are reachable from it, then you can use this algorithm to recognise a string:

Given the start state $s$, set $W := \mathbf{closure}(s)$. (Again, this can be precomputed.)
For each input symbol $a$, set $W := \cup_{s \in W}\,\delta^{*}(w, a)$.
Accept if there is a final state in $W$.

This algorithm looks like it takes $O(k^2n)$ space in the worst case, namely, the space to represent $\delta^{*}$. And the inner loop operation, $\cup_{s \in W}\,\delta^{*}(w, a)$, looks like it should take $O(k^2)$ time in the worst case.
This isn't quite true in the word RAM model, however. Consider that the space needed to store a set of states can be measured in bits; since $k$ is known in advance, the sets like $W$ and the codomain of $\delta^{*}$ can be represented as a bit vector, and set union can be a logical or. So in the word RAM model, the inner loop will actually take $O\left(\frac{k^2}{\log k}\right)$ time in practice.
Having said that, as you correctly guessed, Thompson's construction is not ideal for this use case. It has many advantages (not the least of which is that the space is linear in the size of the input regular expression), but the efficiency of its &quot;obvious&quot; recogniser algorithm is not one of them. As you rightly suspected, it produces a lot of unnecessary states that we can get rid of.
One obvious point is that it's trivial to optimise common &quot;leaf&quot; cases. For example, Thompson's algorithm will turn $a^*$ into a NFA with 4 states, but it should be obvious that you &quot;need&quot; fewer than that, and the complexity of the construction for $E^*$ is only needed because $E$ may be more complex.
Following this reasoning, it is possible, without too much difficulty, to construct an NFA with the following properties:

The number of states is equal to the number of alphabet symbols in the original regular expression (in some formulations, plus one for the start state, but here we will use a set of start states). That is, $a^*a^*ab$ should require exactly 4 states.
There are no $\epsilon$ transitions.
Every transition into a state $s$ has the same label.

Property 1 gives an accurate bound on the number of states which is computable at parse time.
Property 3 means that you can label states with alphabet symbols instead of transitions. Together with property 2, the transition function $\delta$ doesn't need to consider input symbols.
We define a normal NFA (NNFA) to be a 6-tuple $(\Sigma,Q,\delta,I,F,A)$ where:

$\Sigma$ is the alphabet.
$Q$ is a set of states.
$\delta : Q \rightarrow 2^Q$ (or, alternatively, $\delta \subseteq Q \times Q$) is the transition function.
$I \subseteq Q$ is the set of initial states.
$F \subseteq Q$ is the set of final states.
$A : Q \rightarrow \Sigma$ is a function which assigns labels to states.

Then the inner loop of the recogniser algorithm is to set:
$$W := \left\{ s\,|\,w \in W, s \in \delta(w), A(s) = \alpha\right\}$$
This should give you a lot of ideas as to how to implement this in data structures. For example, consider representing $\delta$ as a bit matrix and $A$ as a map from $\Sigma$ to a bit vector, where $A(\alpha)$ is the set of states $q$ which have the label $\alpha$. Then the inner loop becomes a bunch of bit vector unions (i.e. logical or operations) with a final bit vector intersection (i.e. a logical and). In the word RAM model, this is extremely efficient.
As to how to construct a NNFA, it's worth trying to come up with the idea behind it yourself, now that you know that it's possible. As a hint, start with Thompson's construction, and create a new automaton where the &quot;new&quot; states are the $\mathbf{closure}$ of every state which has a terminal transition coming into it. You can then think about how you could compute that automaton without explicitly constructing Thompson's automaton to begin with.
Once you've tried it, the best explanation that I've seen is Chang's PhD thesis. But here's the amazing part: Chang then goes on to give a compressed representation for a NNFA which takes $O(k)$ space, with a construction algorithm that uses $O(k)$ auxiliary space and $O(r)$ time where $r$ is (in some sense) the &quot;size&quot; of the input regular expression.
That effectively answers your question. There is indeed an algorithm which recognises regular expressions, which stores the automaton in $O(k)$ space, where $k$ is linear in the size of the input regular expression, and which takes $O(nk)$ time to recognise a string.