HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

CFG for all strings of a’s and b’s that contain a different number of a’s and b’s

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
numberallcontaincfgdifferentthatforandstrings

Problem

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.

Solution

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.

Context

StackExchange Computer Science Q#110144, answer score: 2

Revisions (0)

No revisions yet.