Algorithm Problems

The problems need to be worked out with answers squared.

Prove that the following languages are not regular using a pumping
lemma.

{0n 1m 0n | m, n ( 0}.

the complement of {0n 1n | n ( 0}

{0m 1m | m ( n}.

{w | w ( {0,1} is not a palindrome}.9

Let

.

gives two rows of 0s and 1s. Consider each row to be a binary number
and let



( C. Show that C is regular.

4. Show that the language F = {w | w is not a palindrome} satisfies the
three conditions of the pumping lemma even though it is not regular.
Explain why this fact does not contradict the pumping lemma.

Show that the class of context-free languages is closed under the
regular operations, union, concatenation, and star.

Show that, if G is a CFG in Chomsky normal form, than for any string w (
L (G) of length n ( 1, exactly 2n – 1 steps are required for any
derivation of w.

Give an example of a language that is not context free but that does
satisfy the three conditions of the pumping lemma. Prove that your
example works. (See the analogous fact for regular languages in Problem
1.37 (page 89).