patternMinor
CFG for all strings of a’s and b’s that contain a different number of a’s and b’s
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.
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.
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.