CODEWITHSUNDEEP
context-free-grammarlexical-analysis
Niyam Shah
Niyam Shah

Reputation: 405

Context free grammar for languages with more number of as than bs

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 ?

Upvotes: 6

Views: 21789

Answers (5)

Anushka Mahajan
Anushka Mahajan

Reputation: 1

S -> SS | aSb ∣ bSa ∣ a

Can this be a solution as well?

Upvotes: 0

Silent
Silent

Reputation: 1

Another simple solution I can think for this would be:

S -> XAX|a

A -> aS|Sa

X -> aXb|bXa|e

For e to be epsilon.

Upvotes: 0

Silvio Bandeira
Silvio Bandeira

Reputation: 1

S → TAT

T → ATb | bTA | TT | ɛ

A → aA | a

T generates any string where #a >= #b (including the empty string). S ensures there is at least one 'a' more than b's at any position.

Upvotes: 0

Dhruv Ghulati
Dhruv Ghulati

Reputation: 3026

Another perhaps simpler solution:

S->A|AAB|BAA|e A->AA | a B->AB | BA | b

Upvotes: 0

blazs
blazs

Reputation: 4845

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.

Upvotes: 16

Related Questions