0
$\begingroup$

Let's say that we have a regular language $L_1$ that is described by a right regular grammar. Now, assume we have a left regular grammar, can we describe the same language $L_1$ or would the left regular grammar produce the reverse of all strings present in $L_1$?

My understanding is that the left regular language would produce a new language $L_2$ containing the reverse of all strings of $L_1$. But since we know that reverse of a language is regular, both right regular and left regular grammars are capable of describing regular languages

Is my understanding correct?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Yes, your understanding is correct:

  • Reversing the rules of your right regular grammar for $L_1$ will produce a left regular grammar for $L_2$, the language consisting of the reverses of the strings in $L_1$.
  • Every right regular grammar can be reversed in this way to form a left regular grammar, and vice versa.
  • This does not give you any way to construct a right regular grammar for $L_1$.
  • Consequently, to show that every language that can be described with a right regular grammar can also be described by a left regular one, you need a different argument.
  • To show that, it is indeed sufficient to show (by different arguments) that
    • the right regular grammars can indeed describe all regular languages, and
    • the reverse of a regular language is always regular.
Improve this answer
$\endgroup$

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.

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