Q 4

===

It was answered, look back the site doesn't allow me to post links.

Q 9

===

Only a is false.

Why a is false: define CNF for 0^r1^r, and calculate the amount of steps it takes you to derive a word of length l. Create an equation for n as a function of l. Choose l such that n is a natural number equal or bigger than the amount of variables in your grammar, and then bloat your grammar as needed in order to get the required number of vars. Done!

Why b is true: Recall the algorithm for checking whether a CFG defines a finite language. We said that if the graph created by the grammar has no circles, the grammar defines a finite language.

This means that the longest path in the parsing tree is of depth n - 1. A binary tree with n-1 depth has 2^n - 1 internal nodes, which means we have one derivation step too much for such a tree.

Q 10

===

Yes.

Any stack with finite depth K over a finite alphabet with r symbols can be simulated using k^r states. So you can build an equivalent NFA using |Q|*k^r states.