Find a grammar that generates strings over {a,b} that contain "ba"

Question

My grammar is G = (Terminals, NonTerminals, Rules, StartingSymbol)

Terminals = $a,b,\lambda$
NonTerminals = $A,B,S$
StartingSymbol = $S$

RULES =

$$\begin{align*} &S\to A\mid B\\ &A\to a\mid aAB\mid\lambda\\ &BB\to B \end{align*}$$

Theses rules are not good, because this grammar can recognize for example $bbb$. I need some tips & tricks to find this grammar.

Answer 1

Try this:

$$\begin{align*} &S\to TabT\\ &T \to \lambda \mid aT \mid bT \end{align*}$$

Answer 2

The strings that you want are precisely those of the form $ubav$, where $u$ and $v$ are words over the alphabet $\{a,b\}$. The most straightforward approach is to let $S$ generate an arbitrary string before ‘turning into’ $baX$, where $X$ is a non-terminal that also generates an arbitrary string. In other words:

$$\begin{align*} &S\to aS\mid bS\mid baT\\ &T\to aT\mid bT\mid\lambda \end{align*}$$

A typical derivation will start with some number $k$ of applications of the productions $S\to aS$ and $S\to bS$; the result at this point will be of the form $uS$, where $u$ is a string of length $k$ (which could be $0$). Eventually, though, you’ll have to apply $S\to baT$ in order to get rid of $S$; at that point you’ll have $ubaT$. Then you must have some number $\ell$ of applications of $T\to aT$ and $T\to bT$ followed by $T\to\lambda$: nothing else is possible. And when that’s done, you’ve produced a word $ubav$, where $u$ has $k$ characters and $v$ has $\ell$.