# right and left linear grammars

1,129

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.

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!

Share:
1,129 Author by

### Tes

Updated on January 24, 2020

• Tes over 3 years

I'm having trouble to solve this following autom. A: 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 over 6 years
What states are acceptor states?
• Tes over 6 years
the acceptor state should be 3, it is noted with an outgoing arrow here
• 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.