# Transform regular grammar in linear grammar

My problem is how can I transform a regular grammar into a linear grammar?

I know that a linear grammar has the form

\begin{align} A &\to w_1Bw_2 \\ A &\to w \end{align}

where $A,B \in N$ and $w,w_1,w_2 \in \Sigma^*$.

• This question is easily solved by reading the corresponding Wikipedia article. Please make it a habit to check obvious references before you post questions. (Maybe it should have been $\Sigma^*$?)
– Raphael
May 28, 2012 at 11:01
• Part of Exercise 6.1.b, due May 31st.
– Raphael
May 30, 2012 at 8:02

A (right) regular grammar is one in which all production rules are of one of the following:

$$B \rightarrow a$$ $$B \rightarrow aC$$ $$B \rightarrow \lambda$$

Where $B$ is a non-terminal, $a$ is a terminal and $\lambda$ is the empty word. A regular grammar is a grammar which is either right-regular xor left-regular. As you have said in a linear grammar one does not require the nonterminals to appear on the far side of the right of the production rules. Therefore, every regular grammar is already a linear grammar.

• ie. Pick $w_2=\lambda$ May 28, 2012 at 10:59
• but how can i modify a regular grammar into a linear grammar?? May 28, 2012 at 11:26
• a regular grammar IS a linear grammar. You don't need to do any transforming. May 29, 2012 at 10:25

regular in what sense?

• If you mean regular in the sense of a regular language then the question is trivial since regular grammar is already a linear grammar.

• If you mean regular in the sense of a customary or usual i.e.

How to transform an arbitrary context-free grammar into a linear grammar?

then this is not possible since there are examples of context free grammars that generate languages that are not recognizable by a linear context free grammar. (e.g. the Dyck language)

(Both answers can easily be found in the corresponding wikipedia article.)

• the question is to transform a regular grammar into a linear grammar with few variables May 28, 2012 at 11:56
• @user1594: what do you mean by "with few variables"? (Also: why any answer here is not enough for you?)
May 28, 2012 at 12:50

Formally, choose $w_1=\varepsilon$ (or $w_2=\varepsilon$) for all rules to obtain a left-regular (or right-regular) grammar.
• I think that his definition is equivalent, as he allows $w_1$ and $w_2$ to be empty. May 29, 2012 at 22:52
• @SamJones: Right. The $^*$ was missing earlier. Editing to adapt.