Theory of Computation Michael Sipser
Chapter 1

Exercise 29
The language is not regular.

Exercise 33
Building a DFA for a language dealing with binary arithmetic

Exercise 40
If is regular, then the language of words that are not proper prefixes of words in is also regular

Exercise 41
The “prefect shuffle” of two regular languages is regular

Exercise 49
A pair of similar languages on a binary alphabet, one regular and one not

Exercise 53
The language of “correct binary addition statements” is not regular

Exercise 54
The language is not regular, but satisfies the pumping lemma

Exercise 57
If is regular, the language of lefthalves of strings in is regular

Exercise 61
We define a family of languages such that a DFA recognizing must have at least states
Chapter 2

Exercise 22
The language is context free

Exercise 23
The language is contextfree

Exercise 26
If a grammar is in Chomsky normal form, for any string of length with , any derivation of has steps

Exercise 33
The language is not contextfree

Exercise 35
If a CFG in Chomsky normal form with variables generates a string under a derivation of or more steps, then is infinite

Exercise 41
Context free languages are not closed under making them “prefixfree” or “extensionfree”

Exercise 44
If and are regular, then is contextfree