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.
1 answer

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.
How many English words
do you know?
do you know?
Test your English vocabulary size, and measure
how many words do you know
Online Test
how many words do you know
Powered by Examplum