Let it be L a regular language.
Prove that exists a fast finite automaton (FFA) M which excepts L.
Definition of FFA:
FFA is a 6-tuple M=$<Q,Σ,P,δ,s,A>$ which:
1. Q is a finite set of states
2. Σ is a finite set of input symbols
3. P is a finite set of pairs in which each pair contains a state and a string ($P⊆Q × Σ^*$)
4. a transition function δ : P → Q (we can go thorugh states by reading strings, and not only by a letter).
5. s is the start state
6. A is the set of accept states
example:
And this is the solution I thought of:
Let it be $L∈L_{REG}$. so we know that $ L∈L_{FA}$. so there is an FA (will be marked as M') which accepts L.
We will define M like this: it will work just like M' for $w=a_1…a_n∈L$, but instead of doing the transitions via reading w's letters (i.e., reading $a_1$, then $a_2$,… and getting to accept state at $a_n$), it will just go straight to an accept state with reading the whole string w.
Two problems that I have here:
1. L isn't necessarily finite, and since I built M by words' transitions, P might be infinite (and it must be finite).
2. Even if I solved the first problem, I still don't know how to formally describe M. how can you describe it?
Best Answer
HINT: Start with a DFA $M_0=\langle Q,\Sigma,\delta_0,s,A\rangle$ that accepts $L$. Now modify $M_0$ to get a FFA $M=\langle Q,\Sigma,P,\delta,s,A\rangle$ that is essentially identical to $M_0$ in its operation. Use $\delta_0$ to define both $P$ and $\delta$.