[SOLVED] prob6

prob6

Problem 6

Proof

I wil first prove: if a language is regular, then it is accepted by a Multistart FA. Proof: Since
it is regular, it can be accepted by an ordinary deterministic FA. Now we add a new start state to
it and make it become the Multistart FA. Because we can start from original start state of the
ordinary deterministic FA and finishes in a Final state, the language is accepted by the Multistart
FA.

Next, we will prove: if a language is accepted by a Multistart FA, then it is regular. Proof:
We can transform theMultistart FA that accepts the language to a Non-deterministic Finite
Automaton(NFA) that still accepts the language. We can add a new state as the start state of the
NFA, and for each original start state in Multistart FA, the new start state transitions to it with
empty string. The other parts of the FA keep the same and the original start states are no
longer start states. Because Multistart FA accepts the language, omputation can starts in a
original start state and finishes in a Final state, for the NFA, we can transition from the start
state to one of the original start states and finishes in a Final state. Thus, the NFA accepts the
language which means the language is regular.

Combining the above two proofs, we have proven that: a language is regular if and only if it is
accepted by a Multistart FA.

Problem 6
Proof