Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

When talking about languages and regular languages.

Can I say that reversal preserved regularity since if the language L is regular, we can generate it by right linear grammar.

Therefore, the reversal language will be the left linear grammar version of L.

Is that true to say?

share|cite|improve this question
Yes, although if you’re writing up a proof, you should offer a little more detail on exactly what you mean by ‘the left linear grammar version’. – Brian M. Scott Nov 12 '12 at 23:31
@BrianM.Scott thank you – Mike Nov 13 '12 at 2:10
You’re welcome. – Brian M. Scott Nov 13 '12 at 2:24
up vote 1 down vote accepted

yes it is regular, to prove this, for any regular language, L, you can find a DFA and by reversing the transitions in the DFA you will get another DFA that accepts the reverse of L.

share|cite|improve this answer
By reversing the transitions of a DFA you don't get a DFA but a NFA. But this suffices to prove that the reversal is regular. – J.-E. Pin Aug 11 '13 at 11:45

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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