Show that if A is regular so is $A^{R}$

Question

I'm stuck on "For any language $A$, let $A^R = {w^R | w \in A}$ Show that if A is regular, so is $A^R$."

According to my research (see references), the steps required to prove this question, are:

1. Reverse all the links in the automaton
2. Add a new state (call it $q_s$)
3. Draw a link labeled with ϵ from state $q_s$ to every final state
4. Turn all the final states into normal states
5. Turn the initial state into a final state
6. Make $q_s$ the initial state

Anyway, I decided to make a toy-example to check if those steps made sense to me.

So here it is :

---

Consider $\Sigma = \{a,b\}$

I want to read $w = {ab}$, However, I'm extrapolating that we can also read $w = \{ab\}^+$.

So I have built an DFA for it :

Then, I followed the instructions and built this NFA :

---

Now the questions :

1- Why do I have to make it as an NFA instead of making an DFA that recognizes $w = {ba}$ or $w = \{ab\}^+$ ?

2- Can i kill the state $q_3$ of this NFA ? It's dead so why it should be there anyway?

3- Why the first state of the NFA transitions with $\epsilon$ ?

Whats really bothering me is the first question. I can make an DFA that recognizes the Reverse of w = "ab". So why everywhere I research says that I must do it as an NFA?

Here's the DFA that recognizes $w = {ba}$, Once Again, I'm extrapolating that we can also read $w = \{ba\}^+$. Not sure if i should assume that, anyway :

"You need at least 10 reputation to post more than 2 links."

So why isnt that DFA enough to prove that if A is regular, so is $A^r$ ?

References :

"You need at least 10 reputation to post more than 2 links." cs.stackexchange.com/questions/3251/how-to-show-that-a-reversed-regular-language-is-regular

Answer 1

1. Why do I have to make it as an NFA instead of making an DFA...

You don't have to, but making an NFA allows you to use $\epsilon$ transitions, which are convenient for making your procedure.

2. Can i kill the state q3...

Sure, but it wouldn't be useful for your proof. Dead states don't hurt anything, and it would be harder to write this step into your procedure.

3. Why the first state of the NFA transitions with ϵ?

Because the FMS you are working from may have had multiple final states, so you need a way to encode multiple potential starting points. Using $\epsilon$ transitions gives you a choice of multiple states.

What you're trying to do is make a procedural proof. In essence, you're trying to show that for every FSM $A$, you can follow some formula to construct a FSM that also accepts $A^R$. If you can always construct a Finite State Machine for $A^R$, then $A^R$ must be Regular.

The machine that results from your process doesn't have to be the most efficient machine or contain the minimum possible number of states. This isn't a work of art, it's a proof of concept: if you can always make an appropriate reversal machine, then your reversal must always be regular. All it must do is work every time to accomplish your proof.

Answer 2

1.) You can make a DFA but the method you mentioned, or any other method for instance, doesn't provide an easy way to create a DFA.

Plus now that we know that NFA = DFA in the computational power if he can design an NFA easily its the same thing.Once you have an NFA convert it to DFA.

One More thing,

Don't think that if there is only one accept state you can just construct a DFA directly( well you can but not by above technique).

Because, as you can see in your toy NFA, there are states through which you don't have transition for some symbols.

They will go to a reject state, but if you are creating a DFA you need to have them in your design

2.) You can kill it but its just optimization but right now we are focused on getting an NFA for reverse language, we can always optimize it later.

3.) In case you have multiple accept states you need to be able to start from any of that, which is why you create a new pseudo start state, and make e-transitions to actual start state.

4.) If you can give directly design a DFA for A^R then of course there is nothing else you need to do to prove A^R is regular,

but you can do this only for a given A, to prove for general A you need to give a procedure to give a DFA for A^R given A.