I'm working on the exercises in "An Introduction to Formal Languages and Automata" 4th Ed textbook by Peter Linz. Since there are too few answers given in the back of the book, I wasn't able to check my work confidently. Although they look like homework, they are actually not; I just want to master the material that I've read. On the other hand, I'm not seeking a complete solution, a hint would be more than enough. Any suggestion would be greatly appreciated. Many thanks in advance.
Note: This is Exercise 5.1 on page 133, 134, and 135.
Best Answer
I didn't understand which problems from the list you want to analyze, so let me make some general remarks.
CFGs are equivalent to a limited form of computer programming. Instead of writing down a grammar it is easier to understand a set of "subroutines" by which one can (in principle) reduce the problem to easier grammar construction subproblems which are further reduced to smaller problems until it is obvious that all necessary transformations are grammatically expressible in CFG form. This is especially true when you care only about the possibility of expressing the language as CFG and not about finding the "best" grammar that constructs the language.
In solving CFG problems it is useful to imagine taking the string and un-building it --- reducing it to the empty string while conserving membership in the language. Often this can be reversed into a procedure for building any word in the language.
Most of the problems in the list take an easily generated language and impose one linear equation or one linear inequality on the numbers of $a,b,c \dots$ in the string. There will be a finite number of basic operations that preserve the value of a function like $3n_a - 5n_b + n_c$ and allow motion through the level sets of this function (such as adding 5 letters $a$ and 3 letter $b$'s, or three $c$ and one $a$, and so on). If there are additional requirements like $a^* b^* c^*$ where there is an ordering on the letters, the operations will involve inserting (or deleting) letters at consecutive positions, such as $ac \to aacccc$. Most of the linearly constrained problems on the list can be done in this way if you consider that operations can be done in stages, by adding extra "clock" letters if necessary that keep track of the different phases of the algorithm, and are removed at the end of the process.