3
$\begingroup$

I am trying to write CFG for all strings on {a,b} that contains different numbers of a’s and b’s? After two hours of brainstorming, I came up with this:

S→A|B
A→aE|aA|EA
B→bE|bB|EB
E→aEbE|bEaE|Λ

I tried running few strings on this, it worked, But then I run string "abbab" and it failed.
Kindly someone point out at my mistake or tell me the correct CFG for this as I don't know how to correct this.

$\endgroup$
2
$\begingroup$

In fact, your grammar is correct and clean!

Here is how your grammar generates $abbab$.

$$S\Rightarrow B\Rightarrow EB\Rightarrow^* abB \Rightarrow abbE\Rightarrow^* abbab $$

Exercise. Show your grammar is correct.

$\endgroup$
  • $\begingroup$ Oh wow, thanks, didn't think of it. By the way, I have one more question, Do I have to delete this post now or what? Because it is not a question anymore, as my CFG was already correct. $\endgroup$ – Tom Jun 2 at 16:59
  • 1
    $\begingroup$ That's actually wrong. You shouldn't delete a question which has been answered. If you delete it, it will get undeleted if anybody notices. $\endgroup$ – Yuval Filmus Jun 2 at 18:48
  • $\begingroup$ @YuvalFilmus Thanks, didn't know this. $\endgroup$ – Tom Jun 2 at 19:06
  • 1
    $\begingroup$ What's important about a question is that it is an interesting problem that is likely to help others (when combined with answers), and your question is that. Anyone wanting to know how to construct the CFG will be helped by this question. $\endgroup$ – gnasher729 Jun 2 at 21:52
1
$\begingroup$

How about this?

$S\to EAE\,|\,EBE$

$A\to a\,|\,aEAEa$

$B\to b\,|\,bEBEb$

$E\to aEb\,|\,bEa\,|\,\Lambda$

The intuition behind it is that every word $w$ of the language can be viewed as a collection, say $(z_i,\,i=1,\ldots,n)$, of balanced sub-strings of $w$, such that $w = z_1 a z_2 a\ldots a z_n$ or $w = z_1 b z_2 b\ldots b z_n$, where $n>1$.

By "balanced string" I mean a string that has the same number of a's and b's. Those sub-strings are produced by the $E$-rule.

Concatenation with $a$ as a separator is produced by the $A$-rule and with $b$ as a separator by the $B$-rule. Because we need to have at least one concatenation operation ($n>1$, otherwise we erroneously produce the empty string), the starting rule applies one of the two.

Update: This answer has a common(?) mistake.

$\endgroup$
  • $\begingroup$ I am trying to run "abbab" on it. But this CFG is not accepting it. Can you run this string? $\endgroup$ – Tom Jun 2 at 13:28
  • $\begingroup$ @Tom, you're right. I wasn't expressing the concatenation operation correctly. I have updated my answer and now "abbab" can be derived. It is the concatenation of two "ab" with a "b" as a separator. $\endgroup$ – frabala Jun 2 at 13:39
  • $\begingroup$ I am still not able to run "abbab". Can you explain it that by using which productions, I can run this string? $\endgroup$ – Tom Jun 2 at 16:13
  • 1
    $\begingroup$ @Tom, it's $S\to EBE\to EbE\to aEbbaEb\to abbab$. $\endgroup$ – frabala Jun 2 at 16:15
  • 1
    $\begingroup$ Although the intuition is nice and correct, the grammar does not generate $aa$ or $bb$. $\endgroup$ – Apass.Jack Jun 3 at 2:24
1
$\begingroup$

Here is a (hopefully) more principled approach. Let us start with a grammar for the language of all strings containing the same number of $a$'s and $b$'s ("balanced"). We can identify such strings as walks in which $a$ gets translated to $\nearrow$ and $b$ gets translated to $\searrow$. We concatenate these arrows horizontally. For example, $aabbab$ is the walk $$ \begin{array}{cccccc} & \nearrow & \searrow \\ \nearrow & & & \searrow & \nearrow & \searrow \end{array} $$

A walk is balanced if it ends up in the Y axis. For every such walk, one of the following cases must hold:

  • The walk is empty.
  • The walk reaches the Y axis at some point in the middle.
  • The walk doesn't reach the Y axis at any point in the middle.

A walk of the second type is a concatenation of two balanced walks, and conversely, the concatenation of two balanced walks is balanced. A walk of the third type is of the form $\nearrow W \searrow$ or $\searrow W \nearrow$, where $W$ is a balanced walk, and conversely, walks of these forms are balanced. This shows that the following grammar generates all balanced walks: $$ W \to \epsilon \mid WW \mid aWb \mid bWa $$

What about unbalanced walks? We will consider walks with more $\nearrow$s than $\searrow$s. There are at least two ways of approaching this problem:

  1. For each such walk, we can consider the last time that the walk reaches the origin. That part of the walk is balanced, and then we must have $\nearrow$, followed either by another balanced walk, or by another walk with more $\nearrow$s than $\searrow$s; and conversely, any walk of these two types is "$\nearrow$-unbalanced".

  2. For each such walk, we can remove $\nearrow$s until we get a balanced walk. Conversely, starting with a balanced walk, if we add at least one $\nearrow$ anywhere, we get an $\nearrow$-unbalanced walk.

A grammar capturing the first type of structure is $$ A \to WaW \mid WaA $$ A grammar capturing the second type of structure is a bit more complicated to state. Let us start with a grammar for at least as many $a$ as $b$s: $$ A \to E \mid EAEAE \mid EaEAEbE \mid EbEAEaE \\ E \to aE \mid \epsilon $$ Here $E$ means "optional $a$s". In order to convert it to a grammar of more $a$ than $b$s we need to add a new symbol $A'$ which enforces adding at least one $a$: $$ A' \to aE \mid aEAEAE \mid EA'EAE \mid EAaEAE \mid EAEA'E \mid EAEAaE \mid \cdots $$ (We let the reader complete the definition.)

Summarizing, if we choose option 1, then we get the following grammar: $$ S \to A \mid B \\ A \to WaW \mid WaA \\ B \to WbW \mid WbB \\ W \to \epsilon \mid WW \mid aWb \mid bWa $$

$\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.