I am supposed to create CFG for this languague:

$L= \{w : w \in \{a, b\}^*, |w_b| = 3k, k \geq 0 \}$

where $|w_b|$ is count of terminals $b$ in $w$.

For example:

aa - OK, no 'b'

abb - wrong, only 2 'b'

aaabbb - OK, 3 times 'b'

aababbb - wrong, 4 times 'b'

abbbbbaaa - wrong, 5 times 'b'

abababbbaaab - OK, 6 times 'b'

and so on...

I can't come up with any solution. Any advice?

My goal is to design context-free grammar, not automaton or regular expression (i don't know how to design automatons or RE yet).

What about CFG

G = {{S,A}, {a,b}, R, S}

where R rules are:

1] S -> S A b A b A b A S
2] S -> A
3] S -> ε
4] A -> a A
5] A -> ε


rule 2] is for cases when there are no 'b' symbols in w

rule 3] is for case of empty string

rule 4] is for adding 'a' symbols between 'b', e.g. baaaabab, babaab

rule 5] is for cases, when there are multiple 'b' next to each other, e.g. abbbaaa

Is this CFG ok?

  • 1
    $\begingroup$ What is your question? $\endgroup$
    – Evil
    Oct 26 '17 at 18:39
  • $\begingroup$ In fact this language is regular and it's easy to design a 4-state DFA accepting this language. Note that CFLs cover Regular sets. $\endgroup$
    – fade2black
    Oct 26 '17 at 18:40
  • 2
    $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$
    – D.W.
    Oct 27 '17 at 4:09
  • 2
    $\begingroup$ The way to tell whether your proposed CFG is correct is to prove it correct. See cs.stackexchange.com/q/11315/755 for the techniques for doing that. $\endgroup$
    – D.W.
    Oct 27 '17 at 4:10
  • 1
    $\begingroup$ Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$
    – Raphael
    Oct 27 '17 at 10:50

Your language is regular. You can create a DFA or NFA for your language, and then convert it mechanically into a regular grammar. As an example, here is a grammar for the language of all even-length words over $\Sigma = \{a\}$, which was generated this way from a DFA with two states:

$$ \begin{align*} &S \to aT \mid \epsilon \\ &T \to aS \end{align*} $$

The two nonterminals $S,T$ correspond to the two states; the starting symbol corresponds to the initial state; the productions $S \to aT$ and $T \to aS$ correspond to the transition function; and the production $S \to \epsilon$ corresponds to $S$ being an accepting state.


Hint: A string with exactly one $a$ would look like this: $$ (\text{any number of } b's)\,a\,(\text{any number of } b's) $$ and a grammar to generate the language of these strings is $S\rightarrow AaA,\ \ A\rightarrow bA\mid \epsilon$.



Your CFG looks correct, but it can be made simpler. The production $S \rightarrow SAbAbAbAS$ can be replaced by $S \rightarrow SbAbAbA$ (i.e. remove the first $A$ and last $S$) . Given any string containing $3k$ $b$'s $(k \ge 1)$, the suffix of the string starting with the third $b$ from the right can be generated by the $bAbAbA$ part. For example, if the string is $aababababbab$, then the rightmost $bbab$ can be generated from $bAbAbA$.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.