-1
$\begingroup$

How can I construct a context-free grammar for the following language?

$$ L = \{ w \in \{a,b\}^* : \#_a(w) = \#_b(w) + 2 \}. $$

Please help me out in this. I am not sure how to approach this question. I would also appreciate general tips on constructing context-free grammars. I find it highly difficult.

$\endgroup$
  • 1
    $\begingroup$ Can you construct a CFG for the language of all words containing an equal number of a's and b's? Try to modify that CFG to accept your new language. $\endgroup$ – Yuval Filmus Apr 28 '16 at 9:45
  • $\begingroup$ You can also construct a PDA and use the canonical construction. $\endgroup$ – Raphael Apr 28 '16 at 11:58
  • 2
    $\begingroup$ Welcome to Computer Science! What have you tried? Where did you get stuck? We do not want to just do your (home-)work for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? You may also want to check out our reference questions. $\endgroup$ – Raphael Apr 28 '16 at 11:59
  • $\begingroup$ @Zoey, go through my answer and try to solve the problem. If you still don't get it, then write what you have attempted, and I will give further hints. In my opinion the problem above does not have very obvious solutions especially for new learners. $\endgroup$ – Shreesh Apr 28 '16 at 15:22
2
$\begingroup$

There are essentially two general tips on constructing context-free-grammars. A wide range of normal context-free languages (those that do not require any tricks) have easy grammars for them. And the tricky one that are present in relatively hard exercises are relatively few and these involve knowing some finite number of tricks to construct grammar for them.

Of course the following two tips won't cover all the problems. Also if you can construct a PDA, theoretically you can construct a CFG with it, but it will involve many more symbols than what most of the exercise problems require.

If you are writing a context-free grammar for a compiler of new language then it is understood that you know the tricks of the trade already. And sometimes the grammars of the new language are not even context-free.

First tip: Look for substrings in the language which are strings in some regular language. For regular languages you need to add rules of the form $A\rightarrow aB$ or $A \rightarrow Ba$ (or $A\rightarrow \alpha B$ or $A \rightarrow B\alpha$) whichever suits your intuition.

Second tip: Look for substrings in the language which need to balance some kind of count/symbols around strings of some other context free language. Then you have to add rules of the form $A\rightarrow aAb\ | \ B$ (or $A\rightarrow \alpha A\beta\ | \ B$).

With these two tips you will be able to construct grammars for many simpler context free language. For example

$S\rightarrow aa\ | \ \epsilon$ for context-free language (which is also regular) of even number of $a$'s.

$S\rightarrow aSb \ | \ \epsilon$ for context-free language of strings of the form $a^nb^n$. Here you need to balance a count.

Unfortunately, the language of balanced parenthesis, which is the variant of the language you are talking about needs a simple trick. Basically any production rule that requires two or more non-terminals is not very intuitive, in my humble opinion, unless the symbols are just placeholders (if there is some recursion involved, you will have difficult time in understanding the language accepted, see some grammars for context-sensitive languages, for example, they are truly difficult to understand if you do not have practice reading them). You have to get down to write a proof to see if the language generated by the grammar is indeed the same.

The language of balanced parenthesis is

$S\rightarrow (S) \ | \ SS \ |\ \epsilon$

or,

$S\rightarrow (S)S\ | \ \epsilon$.

You can easily modify the grammar above to a grammar for language of strings with equal number of $a$'s and $b$'s. That can again be easily modified to another grammar for language of strings with number of $a$'s greater than number of $b$'s by 2. However, proofs that language of grammar is indeed the same as in question will involve some non-trivial logic.

$\endgroup$

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.