Ok, so after wasted time for nothing on this question that I asked yesterday:
proving that a regular language can be accepted by a fast finite automaton
Now comes the more interesting prove:
Let it be M, a fast finite automaton (FFA) which accepts L. prove that L is a regular language.
First, the definition for FFA is in the link above.
I thought of finding an NFA, that will be marked as M', which accepts L.
But I got troubled with the definition of ∆. here is what I thought of:
Q'= Q ∪ {$q'_1$,...,$q'_{|w|-1}: |w|>1 , δ (q,w)=$$q_r$ , (q,w)∈P}.
s'=s, A'=A.
transition function:
let it be (q,w)∈P. lets mark δ (q,w)=$q_r$ if |w|<2 then:
∆(q,w)=δ(q,w)
else:
∆(q,$w_1$)=$q'_1$, ∆($q'_1$,$w_2$)=$q'_2$, ... , ∆($q'_{|w|-1}$,$w_{|w|}$)=$q_r$
Am I getting wrong somewhere? My main concern is about the definition of Q. I want to describe it like this: for every string with length>1 that leads from $q_i$ to $q_r$ at M, I want to add new states according to the string length, so that the transition at M' will be by letters. for example: if |w|=2, I will add one state between $q_i$ to $q_r$. for |w|=3 I will add two states and so on...
You have the right idea, but you need to be more careful to make all of the new states different. For each $p=\langle q,w\rangle\in P$ and each $k\in\{1,\ldots,|w|-1\}$ you want to add a new state $q_{p,k}$, and if $w=a_1\ldots a_{|w|}$ you also want transitions
$$\begin{align*} &q\overset{a_1}\longrightarrow q_{p,1}\;,\\ &q_{p,k-1}\overset{a_k}\longrightarrow q_{p,k}\text{ for }k=2,\ldots,|w|-1\;,\text{ and}\\ &q_{p,|w|-1}\overset{a_{|w|}}\longrightarrow \delta(q,w)\;. \end{align*}$$
You’ll have
$$Q'=Q\cup\{q_{p,k}:p\in P\text{ and }1\le k<|\pi(p)|\}\;,$$
where $\pi(p)$ is the length of the second component of $p$: if $p=\langle q,w\rangle$, then $\pi(p)=|w|$.