CODEWITHSUNDEEP
grammarcontext-free-grammarautomatacomputation-theory
Ghostblade
Ghostblade

Reputation: 145

How to write this CFG?

the question is to construct a CFG which generates language

enter image description here

my solution is: S -> aSb | aS | bS | a | b, however, this grammar can also generate strings like aabb, so how to do it?

Thanks for help.

Upvotes: 1

Views: 2178

Answers (1)

BlackJack
BlackJack

Reputation: 2876

So you want a string of a's then a string of b's, with an unequal number of a's and b's. First, let's ignore the equality condition. Then:

S -> aSb | 0

will generate all strings that start with a's and then b's. This rule guarantees an equal number of a's and b's, or the empty string. Now what we want is either more a's, or more b's, but not both. Because if we wanted one more a AND one more b, we'd just apply S again. So we add two new rules:

A -> aA 
B -> bB

and update S to be:

S -> aSb | A | B

So now we can add an equal number of a and b, or add more a's, or add more b's, but not both. This guarantees inequality, so we're almost done. If you don't need the empty string, you can just stop here. For the null string, we can't do:

S -> aSb | A | B | 0,

because that can lead to S -> aSb -> a0b -> ab, which violates the condition. We also can't do:

A -> aA | 0,

because that can produce S -> aSb -> aAb -> a0b -> ab. So what do we do? The trick is to force S's later expansions to have at least one a or b, like this:

S -> aSb | aA | bB
A -> aA | 0
B -> bB | 0

and that's your solution.

Upvotes: 2

Related Questions