I'm currently having trouble coming with context free grammar to describe this language. My current intuition is to generate an arbitrary amount of a,b,c's on my string and then whenever the character d is added to my string, I add two instances of either a,b,c to my string. However, I'm struggling in defining the instance in which a d is added to my string.
1 Answer
$\begingroup$
$\endgroup$
We have a "reference question" How to prove that a language is context-free? where one of the suggestions is to write the language according to its "nesting structure". Then the grammar follows that structure.
Let us start with the related language $\{\; a^ib^jc^kd^m \mid i +j +k \ge m \;\} = \{\; a^i a^{i'} b^j b^{j'} c^kc^{k'}\, d^kd^jd^i \mid \; \dots \}$. That is, for every $a,b,c$ to the left we may write a $d$ to the right, but we can also skip that $d$. Then the number of $d$'s is at most the sum of the other letters, because every $d$ is matched with another symbol.
If we want to ensure that $i+j+k>m$ (in the original formulation) or $i'+j'+k'>0$ (in my second formulation), I can suggest two approaches. Either build three different grammars, one writing at least one extra $a,b,c$ respectively. Or build a finite state control in the variables of the grammar where the variable not only remembers which symbol it is generating ($a,b,c$) but also whether it has already written the extra symbol without matching $d$.
