CODEWITHSUNDEEP
context-free-grammarformal-languages
ibrahim
ibrahim

Reputation: 3404

constructing CFG

How can I construct a Context-Free Grammer for the language x^a y^b z^2(a+b) where a>=0, b>=0. Thanks for helps...

Upvotes: 0

Views: 708

Answers (3)

cnicutar
cnicutar

Reputation: 182609

Think of it this way

x^a y^b z^2(a+b) = x^a y^b z^2a z^2b = x^a y^b (z^2)^b (z^2)^a

Therefore

S -> xSzz | S1
S1 -> yS1zz | e

Upvotes: 3

Fred Foo
Fred Foo

Reputation: 363487

Observe that for each x and for each y, you need to generate two z's because of the 2(a + b). Also, observe that each string can be viewed as an "inside" part of y's and z's, and an "outside" part of x's and z's.

Since for each y you need two z's, the inside part can be described by (using capitals to denote non-terminal symbols and [] for the empty string):

I --> []
I --> y I z z

Now write a grammar for the outside part in the same way, but referring to I in the base case.

Upvotes: 2

Konrad Rudolph
Konrad Rudolph

Reputation: 545488

There are essentially two cases that you need to treat:

  • You can either add an x at the beginning of the string, in which case you need to add two z’s at the end.
  • Or you can add a y in the middle, in which case you also need to add two z’s at the end.

Try reducing either of these descriptions to a simpler grammer (e.g. a^n b^n) for which you know the solution.

This hint should be enough to deduce the generative grammer.

Upvotes: 1

Related Questions