$\Sigma=\{a,b\}$
L = {w| |w| is a multiple of 4 and b is in the first quarter of w}
I need to find construct a CFG for L, but my partner and I have been struggling with this for several hours to no avail.
If we have a start symbol S, my thought would be to somehow divide S into parts, possible into a first quarter and the last three quarters, ie
$S \rightarrow XY$ where X contains b and Y has three times the length of X. The problem is there is no way to allow for recursivity while implementing this length relation of X and Y.
Any ideas?
I think I've come up with a solution due to some of your ideas
$S \rightarrow TSTTT | bXTTT | \varepsilon$
$X \rightarrow TXTTT | \varepsilon$
$T \rightarrow a|b$