I know how to convert any Left Linear Grammar (LLG) to Right Linear Grammar (RLG) and vice versa. This can be done as follows:
- Reverse "LLG for L" to get "RLG for LR" by changing A → Ba to A → aB
- Convert "RLG for LR" directly to "FA for LR"
- 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
- 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?)