0
$\begingroup$

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^*$.

$\endgroup$
2
  • 1
    $\begingroup$ 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^*$?) $\endgroup$
    – Raphael
    May 28 '12 at 11:01
  • $\begingroup$ Part of Exercise 6.1.b, due May 31st. $\endgroup$
    – Raphael
    May 30 '12 at 8:02
1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ ie. Pick $w_2=\lambda$ $\endgroup$
    – Sam Jones
    May 28 '12 at 10:59
  • $\begingroup$ but how can i modify a regular grammar into a linear grammar?? $\endgroup$
    – user1594
    May 28 '12 at 11:26
  • $\begingroup$ a regular grammar IS a linear grammar. You don't need to do any transforming. $\endgroup$
    – Sam Jones
    May 29 '12 at 10:25
1
$\begingroup$

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.)

$\endgroup$
2
  • $\begingroup$ the question is to transform a regular grammar into a linear grammar with few variables $\endgroup$
    – user1594
    May 28 '12 at 11:56
  • $\begingroup$ @user1594: what do you mean by "with few variables"? (Also: why any answer here is not enough for you?) $\endgroup$
    – jmad
    May 28 '12 at 12:50
0
$\begingroup$

Note that your definition is equivalent to the more informal one from Wikipedia:

[A] grammar is linear if it is context-free and all of its productions' right hand sides have at most one nonterminal.

So every regular grammar is linear by definition. That is why regular grammars are also called right- or left-linear (depending on which one you choose).

Formally, choose $w_1=\varepsilon$ (or $w_2=\varepsilon$) for all rules to obtain a left-regular (or right-regular) grammar.

$\endgroup$
3
  • $\begingroup$ I think that his definition is equivalent, as he allows $w_1$ and $w_2$ to be empty. $\endgroup$
    – Sam Jones
    May 29 '12 at 22:52
  • $\begingroup$ @SamJones: Right. The $^*$ was missing earlier. Editing to adapt. $\endgroup$
    – Raphael
    May 30 '12 at 7:25
  • $\begingroup$ Ah, yes. I didn't notice that it had started without a star. $\endgroup$
    – Sam Jones
    May 30 '12 at 11:08

Your Answer

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

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