Proving that two sets of strings are equal

Question

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.

Answer 1

It is not totally clear what are your main obstacles to get the proof done.

Note that $L_{i,j}^k$ is the set of all strings $w$ on a path $\pi$ from $q_i$ to $q_j$ such that for each intermediate state $q_x$ we have $x\le k$; i.e., all intermediate states have index at most $k$.

Consider state $q_k$. Now either the path $\pi$ does not enter $q_k$ at all: then all indices are at most $k-1$ meaning that $w$ belongs to $L_{i,j}^{k-1}$. Or it may enter $q_k$ one or more times. Thus the path is of the form $\pi: q_i \leadsto q_k \leadsto \dots \leadsto q_k \leadsto q_j$, where the subpaths may start and end in $q_k$, but do not pass that state. So the string $w$ can be partitioned into strings that belong to $L_{i,k}^{k-1}$, $L_{k,k}^{k-1}$, ..., $L_{k,k}^{k-1}$, $L_{k,j}^{k-1}$.

That should prove that $L_{i,j}^{k} = L_{i,k}^{k-1} ( L_{k,k}^{k-1} )^*L_{k,j}^{k-1} \cup L_{i,j}^{k-1}$ (or at least the inclusion from left to right, the other inclusion follows similar argumentation).

With this knowledge the induction is on the subscript $k$, and the induction step is

• If $L_{i,j}^{k-1} = M_{i,j}^{k-1}$ for all $i,j$ then $L_{i,j}^{k} = M_{i,j}^{k}$ for all $i,j$.

This should be obvious, just plug in the equations we have.