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 : AFN

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

  • $\begingroup$ There's' nothing illegal about designing your own FA to solve an instance of the reversal problem. The method you cited, though, has the advantage of providing an answer when an ad hoc attempt might elude you. $\endgroup$ Apr 21, 2017 at 17:46
  • $\begingroup$ Hi! Thanks for the reply, but " when an ad hoc attempt might elude you" ? What does this means? $\endgroup$
    – user70855
    Apr 21, 2017 at 17:49
  • $\begingroup$ It means that your "I'll just come up with a DFA for the reverse language" approach will depend on your cleverness while the algorithm doesn't require any cleverness and will always work. $\endgroup$ Apr 21, 2017 at 17:51
  • $\begingroup$ Why does it require an epsilon transition between q_start and the next state ? $\endgroup$
    – user70855
    Apr 21, 2017 at 17:52
  • $\begingroup$ If your original FA had several final states, since these will eventually become start states, you need a way to go from the new start state to the final states that have been made into start states. $\endgroup$ Apr 21, 2017 at 17:54

2 Answers 2

  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.

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

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

  • $\begingroup$ "which are convenient for making your procedure." Will happen some case that if i dont translate to AFN, i wont be able to prove that A = A^r ? $\endgroup$
    – user70855
    Apr 21, 2017 at 18:28
  • $\begingroup$ I'm unfamiliar with the acronym AFN. What is that? $\endgroup$
    – Ben I.
    Apr 21, 2017 at 18:30
  • $\begingroup$ Sorry, AFN = NFA. $\endgroup$
    – user70855
    Apr 21, 2017 at 18:35
  • $\begingroup$ Will happen some case that if i dont translate the DFA that reads w to an AFN that reads w^r, I wont be able to prove that A = A^r ? $\endgroup$
    – user70855
    Apr 21, 2017 at 18:39
  • $\begingroup$ Any NFA has an equivalent DFA, and any DFA has an equivalent NFA, because the machines are equally powerful. NFAs are just easier to write. It's not that you couldn't create a formula to generate a DFA, it would just be needlessly complex. It's like asking, couldn't I write my chicken recipe using no measuring device but a 50ml pipette? Obviously, you could, but it would make your recipe hard to follow and understand. $\endgroup$
    – Ben I.
    Apr 21, 2017 at 19:37

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 AR then of course there is nothing else you need to do to prove AR 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 AR given A.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.