context-free-grammarinequalities

context free grammar with certain inequalities


What could be the correct Context free grammar for the Language L= {a^i b^j a^k | j< i + k} ?

I want to know about the correctness of following CFG for this-

S-> aaSbA | A | ^
A-> bAa | a

Are there any standard rules for getting strings satisfying j < i + k?

Please help


Solution

  • The usual approach is by breaking it down into simpler languages. Start with the simple repeating languages:

    La = { ai } -> ε | Laa
    Lab = { aibi } -> ε | aLabb

    Now you use those to build up your language. The core of your language is LabLba. That gives you the same pattern, but with j = i + k. So to get <, you need to add at least one a either before or after. So you end up with

    S -> aLaLabLbaLa | LaLabLbaLaa

    Now this grammar is ambiguous, so if you care about that sort of thing, you can refactor it to remove (or at least reduce) ambiguities, but that is another question.