| Chapter 14
|
|---|
14.1 CFG for Theorem 14.2
-
For the union of two languages, let the start symbol go to a choice of two other symbols,
each of which then generates one of the two languages. You know how to do
anbn. To get an idea of how to deal with anb2n, note that b2n is Bn where B = bb.
-
For one of the symbols you need to either push or pop 2 markers instead on 1.
Figure out which symbol and action.
|
14.2 Non-CFL
First confine the arguments in the lemmas to the left side of derivation trees, the part that dominates
a's. That is, if all the a's had to be within some distance of the top, there
would be a limit on how many could be in a string of the language. But there is no such limit.
There can be any number of a's, provided there are more b's and still more c's.
So some a is dominated by a long path that must contain the same nonterminal twice. It
follows that there are derivation trees for the language that look like the
diagram in the theorem but with some a's known to be below the A's.
The uniformity arguments still work so we have unlimited growth, as before, in the number of just
two of the symbols. But we know from the argument above that one of the two must be a.
That means that either the b's or c's do not grow in number and eventually we get
strings in the language with more a's than one of the other symbols, contrary to the
definition of the language.
|
14.6 Countable sets
-
To be a perfect square, a number has to be the square of a non-negative integer. Map it to that
non-negative integer (its square root).
-
0, 1, -1, 2, -2,...
|