0
$\begingroup$

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?

$\endgroup$
8
  • $\begingroup$ 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$. $\endgroup$ Nov 9, 2019 at 7:42
  • $\begingroup$ 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? $\endgroup$
    – Maha
    Nov 9, 2019 at 8:46
  • $\begingroup$ Sorry but I think that regular grammars are by definition linear. $\endgroup$ Nov 9, 2019 at 9:37
  • $\begingroup$ 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)? $\endgroup$
    – Maha
    Nov 9, 2019 at 10:25
  • 2
    $\begingroup$ 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. $\endgroup$ Nov 9, 2019 at 11:21

1 Answer 1

1
$\begingroup$

Answer to the last question of the update.

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.

$\endgroup$
2
  • $\begingroup$ I was talking about converting non-linear grammar of regular language to linear grammar. Your language does not seem to be regular, but context free. $\endgroup$
    – Maha
    Nov 10, 2019 at 11:22
  • $\begingroup$ I misunderstood your question, but at the same time, if you start with a regular grammar, it generates a regular language and you can produce a regular linear grammar for this language. $\endgroup$
    – J.-E. Pin
    Nov 10, 2019 at 20: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.