I am stucked at this problem:
Let $A=(\Sigma, Q, q_1, F, \delta)$ be a finite deterministic automaton (I.e. $\delta:Q\times\Sigma\to Q$) such that $Q=\{q_1,...,q_m\}$.
Let's define foreach $i,j\in\{1,...,m\}$, $k\in\{0,1,...,m\}$
(Note: the $\delta$ below is the extension of $\delta$ to $\Sigma^*$)
$L_{i,j}^k=\{w\in\Sigma^*|\delta(q_i,w)=q_j \land \forall u\in PREFIX(w)-\{\epsilon,w\}, \delta(q_i,u)=q_x\to x\leq k\}$
Now let's define the following sets recursively:
For all $i,j\in\{1,...,m\}$:
$M_{i,j}^0=\{\sigma\in\Sigma|\delta(q_i,\sigma)=q_j\}\cup\begin{cases}
\emptyset, \text{if $i\neq j$} \\
\{\epsilon\}, \text{if $i=j$}
\end{cases}$
For all $i,j,k\in\{1,...,m\}$:
$M_{i,j}^k=M_{i,k}^{k-1}\cdot (M_{k,k}^{k-1})^* \cdot M_{k,j}^{k-1}\cup M_{i,j}^{k-1}$
Prove that for all $i,j\in\{1,...,m\}$ and $k\in\{0,1,...,m\}$ we get $L_{i,j}^k=M_{i,j}^k$.
I've tried to prove it by induction on $k$ but failed.
(Note: I've encountered these sets in the proof of the Theorem that says that every regular language has a regular expression)
Thanks a lot.