What does $k$ mean in regular expressions?
$k$ means that if $w \in R^{k}_{ij}$ then on reading $w$, FA starting from the state $i$ enters the state $j$ and never enters a state $t$ where $t &gt; k$ while reading input $w$. In the book, you learn from, $R^{k}_{ij}$ is defined as the set of all strings that transition the automaton $M$ from $q_i$ to $q_j$ without passing through any state higher than $q_k$.