Search code examples
context-free-grammarcontext-free-language

CFG for language

I'm trying to create a cfg generating following language:

foo+bar

Is This language context-free and could be generated by a cfg? if yes , how could the grammar generating this language be created?

I'm not experienced so much in creating cfg's for cfl's. I would be glad if any help or solution is given

Solution

  • To start you off, do you know how to create a CFG for the language {a^n d^t | n = t}? This will be your starting point.

    S -> aSd | epsilon

    From here, you need to extend what happens when there are more as than ds, or more ds than as. The goal will always be to make sure that for every a or b consumed on the left, a c or d is consumed on the right.

    S -> aSd | aAc | bDd | epsilon

    A is the case where there are more as than ds, D is the other case. In each of these, you you need to consume a left character for every right character.

    There's an additional case, which is the case that either or both of n and t are 0. I'll leave it to you to determine how to handle that.

    Then you'll have to deal with running out of one side's character. For example, if you're in state A, you expect to match as with cs until the as run out and turn into bs. Something like,

    A -> aAc | bCc

    I'll leave the rest to you to figure out.