Question

Problem 3 [20 points Prove that the class of regular languages is closed under reverse. That is, show that if A is a regular language, then AR -[wR | w e A is also regular. [Hint: given a DFA M = (Q,Σ, δ, q0,F) that recognizes A, construct a new NFA (Q', Σ,8,6, F') that recognizes AR.]

Answer 1

Given that A is a regular language.

To show : Reversal of A, denoted by A^R is also regular.

Proof:

Since A is regular, there exists an NFA N that accepts the language A.

We will construct from N, an NFA N' which will accepts the language A^R.

To construct N' from N, first we will invert all the transitions in N. For example, let the NFA N looks like:

After inverting all its transitions, the NFA will look like:

Now, we will make the initial state of N, a final state in N' as follows:

At last, we will add a new state which will have lambda transitions to the final states of N. We will make this state the initial state in N'.

The resulting NFA N' accepts the language A^R.

To observe that resulting NFA N' accepts A^R notice that if any string w is accepted by NFA N, then its reversal denoted by w^R will be accepted by NFA N' because all the transitions in N' are the reverse of N. As the string w traverses across NFA N from start state to final state, the reverse of string will traverse across NFA N' from the final state of N(which is start state in N') to reach the initial state of N(which is the final state in N') and therefore, the reverse of string w will be accepted by N' if w is accepted by N.

Hence there exists and NFA which accepts the language A^R which mean that A^R is regular.

Please give this solution a thumbs up if you find it helpful and comment if you have doubts in it.