# Question regarding Context Free Grammar exercises

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.

-
a) Why do you write "Although they look like homework, they are actually not" but add the homework tag? b) You seem to be posting your solutions. Then what does "I'm not seeking a complete solution, a hint would be more than enough" mean? A hint for solving problems you've already solved? Are you asking us to check your solutions? –  joriki Aug 21 '11 at 9:14
@joriki: a) I added homework tag because I just want to make it clear this is my own homework. While ago, SO at stackoverflow corrected me "homework" are not always assignment from class. Also I added "they are not homework" because I'm afraid of someone might think I'm taking my assignment from classes and post them here. b) Yes, I asked for check my solution, but not correcting it. That's why I meant "hint". Let's say I got problem (g) wrong, a "hint" would help me point out "why" it was wrong. A "complete solution" means someone correct my work. Anyway, sorry for the confusion. –  Chan Aug 21 '11 at 10:16
@joriki: If my question is too confusing, I'm willing to edit it. And thanks for pointing that out, in fact I've just realized I'm very bad at writing my question. –  Chan Aug 21 '11 at 10:26
WHen they just ask to prove that a language is context free, it is sometimes easier to produce a PDA, then to produce a CFG. Obviously, sometimes it's easier to produce a CFG then to produce a PDA. I just rapidly checked some of your solutions and they see fine. However, you are forgetting one tiny little detail, and that is to mention which starting variable you choose. Of course in this context it is easy to see that you chose S for this, but try to include it nevertheless. –  sxd Aug 21 '11 at 12:14
@Dimitri Surinx: I totally forgot about PDA ^_^. I will explicitly state S = "starting symbol" from now on. Thanks a lot. –  Chan Aug 21 '11 at 20:28

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.

-
Many thanks for the comment. I agree these problems are all similar to each other. However, I work them all out because I just want to make sure that I understand concept correctly. Whichever problem catches your eyes and doesn't seem right, please let me know. –  Chan Aug 22 '11 at 1:42

$n\geq 0,m\geq0$ $L=\{a b:2n\leq m\leq 3n\}$

-

As for the first question 7(a), on taking a quick look at it, the grammar written by you generates the language containing b (S => T => Tb => T)

S -> aSb | T
T -> Tb | a | aa | aaa | epsilon

However, the one suggested below as in the text seems to not do so.

S -> aA | aaA | aaaA | epsilon
A -> aAb | B
B -> Bb | epsilon

Could the one in the text possibly be a mistake?

-