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