right and left linear grammars


The actual language you came up with is not correct! You can immediately see it from the $a,b$ loop between states 1 and 2, which suggests that any word in the form $<prefix> (ab)^* <suffix>$ works for some appropriate prefix and suffix, whereas $b^*a^*b^*$ can only produce a finite number of $ab$ repetitions.

Instead, the actual language is:

  1. Any number of $0$ or more $b$, which keep you on state $1$, followed by
  2. Exactly $1$ $a$, which moves you to state $2$, followed by
  3. Any number of $0$ or more $b^*a$, which take you back to state $1$, and again to state $2$, followed by
  4. Exactly $1$ $a$, which moves you to state $3$, followed by
  5. Any string, which will leave you on state $3$.

So, $\left(b^*a\right)~\left((b^*)a\right)^*~a~(a|b)^*$. Can you find a right and a left linear grammar for that? You can work from the language and, try first to see how you can produce $(b^*a)$, and $\left(b^*a\right)~\left((b^*)a\right)^*$...

Or, you can notice from the automaton that two consecutive $a$ are necessary and sufficient to move you from state $1$ to state $3$; you can have anything before or after that pair of $a$ and still accept. This suggests an alternative expression for the language, $(a|b)^*aa(a|b)^*$, that's easier to turn into a grammar!

Author by


Updated on January 24, 2020


  • Tes
    Tes over 3 years

    I'm having trouble to solve this following autom. A:

    enter image description here

    1. The language for this machine: I have $L(A) = \{b^*a^*b^*\}$, is that correct?

    2. A right linear grammar $L(G_1)=L(A):$ I have created this grammar:
      $S→bS\\ S→aS_1 \\S_1→aS_2 \\S_1→bS\\ S_2→aS_2\\ S_2→a\\ S_2→bS_2, \\S_2→b$

      Is that correct?

    3. A left linear grammar $L(G_2)=L(A)$: Can I maybe just reverse the right linear grammar $G_1$ like this?
      $S→Sb\\ S→S_1a \\S_1→S_2a \\S_1→Sb\\ S_2→S_2a\\ S_2→a\\ S_2→S_2b, \\S_2→b$

    • Brian M. Scott
      Brian M. Scott over 6 years
      What states are acceptor states?
    • Tes
      Tes over 6 years
      the acceptor state should be 3, it is noted with an outgoing arrow here
  • Tes
    Tes over 6 years
    Thank you for you help! The language is as you said (a,b)^*aa(a,b)^*. My left linear grammar is correct, but just coincidentally for this case. Reversing the right linear grammar doesn't work.