'TOC Problem : Context Free Grammar Design

I want to design CFG for a language that is defined by

L= { w | {a,b,c}* where w= a^i b^j c^k and i+j>k }

Case where i+j=k was easy, however I cannot figure how the case for i+j>k.

automatacomputation-theorypushdown-automatonautomata-theorycfg


Solution 1:[1]

We can start with a grammar for i + j = k:

S := aSc | T
T := bSc | e

If we want i + j > k, we need either at least one extra a or at least one extra a. We can assume each in turn and combine them into one grammar:

A := aW
W := aW | aWc | X
X := bX | bXc | e

B := aB | aBc | Y
Y := bZ
Z := bZ | bZc | e

S := A | B

The production for S nondeterministically chooses between guaranteeing an extra a or an extra b. A/W/X guarantee at least one extra a and allow any number of extra a and b. B/Y/Z guarantee at least one extra b and allow any number of extra a and b.

A/Y require the extra symbol. W/X/B/Z guarantee at least as many a+b as c.

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1 Patrick87

Related Questions