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?

Improve this question
$\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$
    – Vimal Patel
    Commented 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$
    – RajS
    Commented Nov 9, 2019 at 8:46
  • $\begingroup$ Sorry but I think that regular grammars are by definition linear. $\endgroup$
    – Vimal Patel
    Commented 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$
    – RajS
    Commented 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$
    – reinierpost
    Commented Nov 9, 2019 at 11:21

1 Answer 1

Reset to default
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.

Improve this answer
$\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$
    – RajS
    Commented 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
    Commented Nov 10, 2019 at 20:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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