Cheat Sheet & Practice

Product of “parity of $a$’s” (2 states) and “last symbol is $b$” (2 states): 4 states $(E/O, b?/\neg b)$. Start $(E, \neg b)$; accept $(E, b)$. All four states are reachable and distinguishable, so 4 is minimal.

Yes: $(aa)^*(bb)^* \cup a(aa)^*b(bb)^*$. Only the parity of the total length matters, plus the order constraint $a^*b^*$.

Not regular: if it were, its complement intersected with $a^*b^*$, namely $\{a^nb^n\}$, would be regular. Context-free: $S \to aSb \mid A \mid B$, $A \to aA \mid a$, $B \to bB \mid b$ (generate a balanced core, then extra $a$’s or extra $b$’s).

$\{1\} \xrightarrow{a} \{1,2\}$, $\{1\} \xrightarrow{b} \emptyset$; $\{1,2\} \xrightarrow{a} \{1,2\}$, $\{1,2\} \xrightarrow{b} \{1\}$; $\emptyset$ loops. Accept $\{1,2\}$. The language is $a(a \cup ba)^*$: start with $a$, every $b$ is followed by an $a$, end with $a$.

Take $s = a^pb^{p+1}c^{p+2}$. Since $|vxy| \le p$, the window never contains both $a$’s and $c$’s. If $v$ or $y$ contains two kinds of symbols, pumping up puts symbols out of order. Otherwise let $\alpha, \beta, \gamma$ be the numbers of $a$’s, $b$’s, $c$’s in $vy$:

• $\alpha \ge 1$ (so $\gamma = 0$): pump up ($i = 2$). If $\beta \ge 1$ the $b$-count becomes $\ge p+2 = k$; if $\beta = 0$ the $a$-count becomes $\ge p+1 = j$. Either way $i \lt j \lt k$ breaks.
• $\alpha = 0$, $\beta \ge 1$: pump down ($i = 0$); the $b$-count drops to $\le p$, the $a$-count.
• Only $c$’s: pump down; the $c$-count drops to $\le p+1$, the $b$-count.

$j = i + k$ means $b^j = b^ib^k$: $S \to XY$, $X \to aXb \mid \varepsilon$, $Y \to bYc \mid \varepsilon$.

Pass 0 marks $\{A,C\},\{A,D\},\{B,C\},\{B,D\}$. $\{A,B\}$: on 0 → $\{B,A\}$, on 1 → $\{C,D\}$. $\{C,D\}$: on 0,1 → $\{D,C\}$. Neither ever gets marked: $A \equiv B$ and $C \equiv D$. Minimal DFA: 2 states — the language is “contains at least one 1”.

Undecidable by Rice (“$L(M)$ contains a palindrome” is a nontrivial language property). Recognizable: dovetail $M$ over all palindromes (run $i$ steps on each of the first $i$ palindromes, for $i = 1, 2, \dots$); accept when one is accepted.

Undecidable, by reduction from PCP. Given dominoes $[t_i / b_i]$, build $G$ with rules $S \to t_i\,S\,b_i^R \mid t_i\,\#\,b_i^R$ for each $i$ ($\#$ a fresh symbol). $G$ generates exactly the strings $t_{i_1}\cdots t_{i_n}\,\#\,(b_{i_1}\cdots b_{i_n})^R$. Such a string is a palindrome iff the part before $\#$ is the reverse of the part after it, i.e. iff $t_{i_1}\cdots t_{i_n} = b_{i_1}\cdots b_{i_n}$ — a match. So a decider for this problem would decide PCP.

Rice does not apply — this is a property of the machine’s behaviour, not of $L(M)$. It is still undecidable, by reduction from $A_\text{TM}$: given $\langle M, w\rangle$, build $M'$ that writes $w$ on its tape using a renamed copy of $M$’s alphabet containing no $1$, simulates $M$ on $w$ (never writing $1$), and writes a $1$ only if $M$ accepts. Then $M'$ writes a $1$ iff $M$ accepts $w$.

In NP: certificate = two distinct satisfying assignments. Reduction from SAT: given $\varphi(x_1..x_n)$, output $\varphi' = \varphi \land (y \lor \bar y)$ with a fresh variable $y$. Each satisfying assignment of $\varphi$ gives two of $\varphi'$ (any $y$), and $\varphi'$ is satisfiable only if $\varphi$ is.

First: true (compute $f(w)$, then verify for $B$). Second: false — $B$ is NP-hard, but it might not be in NP (e.g. $B = \textit{HALT}_\text{TM}$, to which SAT reduces).

Neither. Not regular: $L = \{a^nb^n\}$ — its complement (strings not of the form $a^*b^*$, plus $a^mb^n$ with $m \ne n$) is context-free, but $L$ is not regular. Not deterministic: $L = \{ww^R : w \in \{a,b\}^*\}$ — its complement (odd-length strings, plus even-length non-palindromes: $S \to aSa \mid bSb \mid aXb \mid bXa$, with $X$ generating every even-length string) is context-free, yet $L$ is not a DCFL.