2022 October 5,

CS 254: Day 10

Carleton College, Joshua R. Davis

There are four problems to be handed in. The first two problems are fairly standard pumping lemma problems. On an exam, you may be expected to do such problems quickly and precisely. If you want more practice, then do more problems from the book, or consult the prefect or me.

A. Problem 2.30a (about 0ⁿ1ⁿ0ⁿ1ⁿ).

B. Problem 2.31 (about palindromes with equal numbers).

The third problem is related to the proof of the CFL pumping lemma.

C. Problem 2.35 (about Chomsky normal form). (Hint: Use the result of problem 2.26.)

The fourth problem is related to Problem 1.54. It's easier than it may look.

D. Problem 2.36 (about a pumpable language that isn't context-free).