Theory of Computation

Exercise 29 The language $\setbuilder{www}{w \in \set{a, b}^*}$ is not regular.
Exercise 33 Building a DFA for a language dealing with binary arithmetic
Exercise 40 If $A$ is regular, then the language of words that are not proper prefixes of words in $A$ 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 $F = \setbuilder{a^i b^j c^k}{i,j,k \geq 0 \text{ and if } i = 1, \text{ then } j=k}$ is not regular, but satisfies the pumping lemma
Exercise 57 If $A$ is regular, the language of left-halves of strings in $A$ is regular
Exercise 61 We define a family of languages $C_k$ such that a DFA recognizing $C_k$ must have at least $2^k$ states

Exercise 22 The language $C = \setbuilder{x\#y}{x, y \in \set{0,1}^* \tand x \neq y}$ is context free
Exercise 23 The language $D = \setbuilder{xy}{x,y \in \set{0,1}^* \tand \abs{x} = \abs{y} \tand x \neq y}$ is context-free
Exercise 26 If a grammar $G$ is in Chomsky normal form, for any string $w \in L(G)$ of length $n$ with $n \geq 1$ , any derivation of $w$ has $2n-1$ steps
Exercise 33 The language $F = \setbuilder{a^i b^j}{i = kj \text{ for some } k}$ is not context-free
Exercise 35 If a CFG in Chomsky normal form with $b$ variables generates a string under a derivation of $2^b$ or more steps, then $L(G)$ is infinite
Exercise 41 Context free languages are not closed under making them “prefix-free” or “extension-free”
Exercise 44 If $A$ and $B$ are regular, then $A \diamond B = \setbuilder{xy}{x \in A, y \in B \tand \abs{x} = \abs{y}}$ is context-free