The question is to develop a context free grammar for language containing all strings having more number of As than Bs.
I can't think of a logical solution . Is there a way to approach such problems , what can help me approach such problems better ? Can someone suggest a logical way to analyse such grammar problems ?
The following grammar generates all strings over {a,b}
that have more a
's than b
's. I denote by eps
the empty string.
S -> Aa | RS | SRA
A -> Aa | eps
R -> RR | aRb | bRa | eps
It's obvious it always generates more a
's than b
's. It's less obvious it generates all possible strings over {a,b}
that have more a
's than b
's
The production R -> RR | aRb | bRa | eps
generates all balanced strings (this is easy to see), and the production A -> Aa
generates the language a*
(i.e. strings with zero or more a
's).
Here's the logic behind the grammar. Notice that if w=c1,c2,c3,...,cn
is a string over {a,b}
with more a
's than b
's then we can always decompose it into a concatenation of balanced strings (i.e. equal number of a
's and b
's, which includes the empty string) and strings of the form a+
.
For example, ababaaaba
= abab
(can be generated by R
),aaa
(can be generated by A
),ba
(can be generated by R
).
Now notice that the production S -> Aa | RS | SRA
generates precisely strings of this form.
It suffices to verify that S
covers the following cases (because every other case can be covered by breaking into such subcases, as you should verify):
[a][balanced]
: use S => SRA => AaR
.[balanced][a]
: use S => RS => RA => RAa
.[balanced][a]balanced]
: use S => SRA => RSRA => RAaR
.