A context-free grammar for all strings that end in b and have an even number of bs

Question

I'm trying to find CFG's that generate a regular language over the alphabet {a b}

I believe I got this one right: All strings that end in b and have an even number of b's in total:

$\qquad S \to SS \\ \qquad S \to YbYb \mid \varepsilon \\ \qquad Y \to aY \mid \varepsilon$

However, Im not sure how to accomplish this with an odd number of b's.

So for example, how could I find a CFG that generates all strings that end in b and have an odd number of b's in total: So far I have this,

$\qquad S \to SS \\ \qquad S \to YYb \mid \varepsilon \\ \qquad Y \to abY \mid baY \mid \varepsilon$

But this can generate abababb so it's incorrect and Im stumped at this point.

Answer 1

Assuming $\Sigma = \{a, b\}$ this probably should do the trick

$\qquad S \to Yb\\ \qquad Y \to YXbXb \mid X \mid \varepsilon \\ \qquad X \to Xa \mid \varepsilon$

This should work because Y always has even number of b's and S adds one b at the end which makes number of b odd.

Answer 2

There is an easy and very natural way how to derive a context-free grammar $G=(V,\Sigma,R,S)$ from a DEA $M=(Q,\Sigma,\delta,q_0,F)$. We set

• $V=Q$
• $S= q_0$
• $R$ consists of the following rules:
  • for all $X\in Q$ and $a\in \Sigma$ with $Y=\delta(X,a)$ we add the rule $X \to aY$
  • for all $X\in F$ we add the rule $X \to \varepsilon$
  • there are no other rules in $R$

It's an easy exercise to show that $L(G)=L(M)$. With this technique you can now build your automaton first (which is an easy two-state example in your case), and then apply this construction.

Answer 3

You mention correctly that the language is regular, so a regular grammar is the easiest way to go:

$\qquad \begin{align} S &\to aS \mid bT \\ T &\to aT \mid bS \mid b \end{align}$

This solution uses the "counting" trick: we store in the "state" (whether we have $S$ or $T$ in the sentential form) whether we have generate an even number of $b$ so far.

Answer 4

In both cases (even number of b's and odd number of b's) the language cannot contain empty string ε as in the question in both cases it is mentioned that each string must ends in b. But ε does not end in b, therefore:

1) For even number of b's and ends in b:

S → TbTb

T → aT | bTb | ε

2) For odd number of b's and ends in b:

S → Tb

T → aT | bTb | ε