I stumble across this problem:

enter image description here
Give right linear grammar.

The solution given was simple:

$S\rightarrow bA$
$S\rightarrow aS$
$A\rightarrow \lambda$
$B\rightarrow bA$
$A\rightarrow aB$

Earlier I came across problems specified in this post, which involves applying Arden's theorem to left linear and right linear equations to find regular expressions. So I thought whether I can come up with left linear grammar for this. I tried and come up with this grammar:

$S\rightarrow \epsilon | Sa$
$A\rightarrow Sb|Bb$
$B\rightarrow Aa$

I was doubting if it is correct. So I tried operating both grammars on string "ab".

For right linear grammar, instantaneous description will be:

$S\Rightarrow aS \Rightarrow abA\Rightarrow ab$

For left linear grammar, I felt it should be:

$A\Rightarrow Sb\Rightarrow Sab\Rightarrow ab$

Book by Peter Linz explains how we can convert between right linear grammar and automaton on page 94,95. So I was thinking if its possible to convert between automaton and left linear grammar.

As you can see, above derivation in left linear grammar doesnt start with $S$ but ends with $S$ (i.e. uses production $S\rightarrow \epsilon$ in the end). So is it correct to think as valid derivation and legit left linear grammar? Also can we interpret it as something like bottom up derivation? I know I have not read anything like this in reference books, but was just giving free thoughts.

  • $\begingroup$ What is your question exactly? $\endgroup$ – reinierpost Jul 2 '18 at 12:47
  • $\begingroup$ Ok, I typed period instead of question mark. Now corrected. Repeating the questions: Is that left linear grammar correct (especially after realizing that the derivation for "ab" does not start with $S$)? Is that derivation correct? $\endgroup$ – anir Jul 2 '18 at 18:51

Your Answer

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

Browse other questions tagged or ask your own question.