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

  • answered 2022-04-27 20:40 Patrick87

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