Search code examples
compiler-constructioncontext-free-grammarcontext-free-language

Context-Free Grammar of language {a^i b^j c^i}

During exercise, I am supposed to write a Context-Free Grammar for the following language:

enter image description here

I am not sure I fully understand the approach, but here is what I got.

Since we need at least 1 c surrounded by any equal numbers of a's and b's (could be zero) I came up with the following CFG:

T --> aCb | aTb | C
C --> cS | cC
S --> empty

From above, I can for instance never create a string, without atleast 1 c in it. But I can create a string with just a c and no a's or b's. Similar I can create strings with aa...c...bb (with any number of a's and b's with just 1 c in between) as well as any strings similar to the previous but with any number of c's as well.

However, I feel like this CTF is somewhat more complex that what needs be. Can anyone tell me how to improve if, or in the case it is wrong - what I am missing?

Edit: after some good inputs from rici what I arrive at are now:

T --> aTb | cC
C --> cC | empty

By removing any redundancy (such as aCb which could be achieved through aTb and C) as well as the non-terminal S.

Solution

    1. Eliminate S. It's not doing anything other than collecting a paycheque.

    2. T → a C b is redundant since you already have T → a T b and T → C, which obviously can do the same thing (by applying them in that order).