3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Why don't you create regular grammars? $\endgroup$ – Raphael Oct 22 '12 at 13:45
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ ah I see how you got that, thanks for the help! Hmm, would something like this work as well? S->YYb|empty, Y-> aX|bbX|empty $\endgroup$ – user3115 Oct 19 '12 at 7:22
  • $\begingroup$ I guess not because you assume that S might be empty string. In empty string number of b is even. Also you are missing X in your comment grammar. And looks like you won't be able to get to babb $\endgroup$ – Bartosz Przybylski Oct 19 '12 at 7:25
4
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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 | ε

$\endgroup$
  • 1
    $\begingroup$ Welcome to the site! I didnt check closely, but your answer seems to be correct. It would be improved by an explanation of how it works, especially since there are already three other answers giving alterantive grammars. $\endgroup$ – David Richerby Dec 25 '18 at 21:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy