I know how to convert any Left Linear Grammar (LLG) to Right Linear Grammar (RLG) and vice versa. This can be done as follows:

  1. Reverse "LLG for L" to get "RLG for LR" by changing A → Ba to A → aB
  2. Convert "RLG for LR" directly to "FA for LR"
  3. Reverse "FA for LR" to get "FA for L" by
    • Change starting state to final state
    • Reverse direction of each transition
    • Create a new start state with $\epsilon$-transitions to all accepting states
  4. Convert "FA for L" directly to "RLG for L"

Similar approach can be derived for converting "RLG for L" to "LLG of L".

LLGs and RLGs are regular grammars. Though LLGs are left recursive and RLGs are right recursive, when we say right recursive and left recursive, they also include CFGs too (right?). So can we have similar procedures for converting left recursive CFGs to right recursive CFGs and vice versa. Or in fact any left recursive grammar to equivalent right recursive grammar and vice versa, regardless of to which type of Chomsky hierarchy they belong?

(Extra question: Is there any other procedure to covert LLG to RLG and vice versa simpler than the above?)

  • $\begingroup$ I'm not sure your procedure works. Reversing the automaton's transitions seems optimistic when it works with a stack. $\endgroup$ – xavierm02 Dec 30 '16 at 21:09
  • $\begingroup$ The way I see it, being left or right linear is a good thing: You have a very specific shape. But being left or right recursive is a bad thing: it just tells you that for some non-terminal, there is a rule $X\to X\alpha$ where $\alpha$ can be any word. So you're essentially asking if we can turn any grammar with a left-recursion problem into one with a right-recursion problem... Note that if you want to ensure the existence of non-right/left-recursive grammars, the existence of greibach normal forms answers the question. $\endgroup$ – xavierm02 Dec 30 '16 at 21:30
  • 1
    $\begingroup$ What are "left recursive" and "right recursive" grammars? $\endgroup$ – Yuval Filmus Dec 31 '16 at 1:29
  • $\begingroup$ The linear part can avoid mirror image ánd automata if you change $A\to aB$ to $B\to Aa$. And replace $S \to aB$ by $B\to a$ (and vice versa). $\endgroup$ – Hendrik Jan Dec 31 '16 at 2:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.