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


image ends

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?


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$.

  • $\begingroup$ Wow, I can't believe I didn't think about it. an FFA is actually a kind of FA. I just needed to define P with letters only. tnx! $\endgroup$ – John Nov 25 '15 at 22:01
  • $\begingroup$ @John: You’re welcome! $\endgroup$ – Brian M. Scott Nov 25 '15 at 22:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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