# Does every regular language have a linear grammar?

Some definitions and facts (from Wikipedia):

1. A linear grammar is a context-free grammar that has at most one nonterminal in the right hand side of each of its productions.

2. the left-linear or left regular grammars, in which all nonterminals in right hand sides are at the left ends;

3. the right-linear or right regular grammars, in which all nonterminals in right hand sides are at the right ends.

4. Collectively, these two special types of linear grammars are known as the regular grammars; both can describe exactly the regular languages.

Doubts

1. Fourth fact used word "collectively" and then "both". What does it actually mean?

• there is both right linear and left linear grammar for all regular languages
• there is either right linear or left linear grammar for all regular languages
2. Can all non-linear regular grammars be converted into linear regular grammars? (Is there any systematic procedure for that?)

Update

I got it now how we can translate RLG to LLG and vice versa. So any given regular language has both RLG and LLG. Now the second question is remaining: Can all non-linear regular grammars be converted into linear regular grammars?

• Right linear grammars have straight forward translation to and from DFA. And may be left linear grammar for given regular language $L$ can be constructed from reversing right linear grammar of $L^R$. – Vimal Patel Nov 9 '19 at 7:42
• Yeah I got it now that we can translate RLG to LLG. So any given regular language has both RLG and LLG. Now the second question is remaining: Can all non linear regular grammar be converted into a linear language? – anir Nov 9 '19 at 8:46
• Sorry but I think that regular grammars are by definition linear. – Vimal Patel Nov 9 '19 at 9:37
• ohh indeed!!! I got confused because I read this: "language of non-linear grammar does not necessarily meant to be non-regular, because there may exist regular grammar for that language". Cant there be a non linear grammar for a regular language? If yes, can we convert it to right linear grammar (or left linear grammar)? – anir Nov 9 '19 at 10:25
• 1) Yes, there can be a non linear grammar for a regular language, e.g. S- > SS | a. 2) No, there is no systematic method for converting every such grammar to a regular one: regularity of context-free languages is undecidable. – reinierpost Nov 9 '19 at 11:21

The grammar $$S \to aSb + 1$$ is linear, but it generates the nonregular language $$\{a^nb^n \mid n \geqslant 0\}$$. Therefore, it cannot be converted into a regular linear grammar.