2
$\begingroup$

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?

  • 1
    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’.2012-11-12
  • 0
    @BrianM.Scott thank you2012-11-13
  • 0
    You’re welcome.2012-11-13

1 Answers 1

1

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.

  • 0
    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.2013-08-11