# Proving that two sets of strings are equal

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.

• What is the meaning of these sets? – Raphael Dec 14 '15 at 12:31
• @Raphael I've encountered these sets in the proof of the theorem that says: every regular language has a corresponding regular expression. My university book claims that the sets are the same and doesn't bother to prove why they are the same. – MathNerd Dec 14 '15 at 12:32
• In the definition of $L^k_{i,j}$ the typing for $\delta$ seems incorrect. Since the question is sort of a flurry of notation, you probably want $\delta : Q\times \Sigma^* \to Q$. – Louis Dec 14 '15 at 12:35
• @Louis The $\delta$ in $L_{i,j}^k$ is the extension of $\delta$ to $\Sigma^*$. – MathNerd Dec 14 '15 at 12:38
• @MathNerd: I'm aware, but really the obligation is on you, since you didn't bother to write things out. – Louis Dec 14 '15 at 12:39

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.

• Thanks, Intuitively I understand that it says what you wrote but I cannot prove it rigorously. How can I show that $L_{i,j}^k=M_{i,j}^k$ by showing $L_{i,j}^k\subseteq M_{i,j}^k$ and $M_{i,j}^k\subseteq L_{i,j}^k$. I've tried induction but I failed to show it. – MathNerd Dec 14 '15 at 12:51
• I see. Only inclusions for the $L_{ij}^k = \dots L_{ij}^{k-1} \dots$ side need to be proved. Stepping between $M_{ij}^k$ and $L_{ij}^k$ is then easy. – Hendrik Jan Dec 14 '15 at 15:37