0
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ What is the meaning of these sets? $\endgroup$
    – Raphael
    Dec 14, 2015 at 12:31
  • $\begingroup$ @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. $\endgroup$
    – MathNerd
    Dec 14, 2015 at 12:32
  • $\begingroup$ 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$. $\endgroup$
    – Louis
    Dec 14, 2015 at 12:35
  • $\begingroup$ @Louis The $\delta$ in $L_{i,j}^k$ is the extension of $\delta$ to $\Sigma^*$. $\endgroup$
    – MathNerd
    Dec 14, 2015 at 12:38
  • 1
    $\begingroup$ @MathNerd: I'm aware, but really the obligation is on you, since you didn't bother to write things out. $\endgroup$
    – Louis
    Dec 14, 2015 at 12:39

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – MathNerd
    Dec 14, 2015 at 12:51
  • $\begingroup$ 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. $\endgroup$ Dec 14, 2015 at 15:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.