FIT2014 Unit Cheatsheet

Context: FIT2014_MOC · the WHOLE unit in one re-read — languages → logic → automata → grammars → parsing → Turing machines → decidability → complexity → NP-completeness. Every claim is hand-derivable; links for depth only.

Quick Revision

• 🎯 Objective: match the claim’s SHAPE to a formula or proof blueprint ➔ derive in \begin{aligned}, seal with Q.E.D.
• ⚠️ Key Constraint: hypothesis discipline — every rule here has a precondition; marks die when a rule fires without it (infinite vs finite, regular vs context-free, decidable vs recognisable, ${\le }_m$ vs ${\le }_P$).

1️⃣ Languages and Words

• Alphabet & word ➔ $\Sigma$ finite non-empty; a word is a finite sequence over $\Sigma$; $\epsilon$ is the empty word · precondition $\varnothing \ne \{\epsilon \}$ — the empty language has no words, the language $\{\epsilon \}$ has one.
• Closure ➔ ${\Sigma }^{\ast }=$ all finite words including $\epsilon$; $x^0=\epsilon$; $|{\Sigma }^{\ast }|$ is countably infinite for any finite $\Sigma$.
• Language ➔ any $L\subseteq {\Sigma }^{\ast }$ · precondition membership must be decidable by definition, not by intuition — state the defining predicate.
• Named test languages ➔ EVEN-EVEN · DOUBLEWORD $\{ww\}$ · PALINDROME · EQUAL ($\#\mathtt{a}=\#\mathtt{b}$) · HALF-AND-HALF (${\mathtt{a}}^n{\mathtt{b}}^n$-style split).

2️⃣ Propositional Logic → CNF Encoding

• Connectives ➔ $\neg ,\wedge ,\vee ,\Rightarrow ,\iff$; $A\Rightarrow B\equiv \neg A\vee B$ · precondition for CNF conversion — implications must be eliminated before De Morgan.
• De Morgan ➔ $\neg (A\wedge B)\equiv \neg A\vee \neg B$, $\neg (A\vee B)\equiv \neg A\wedge \neg B$; extends to $n$ terms by induction, not by assertion.
• DNF ➔ OR of ANDs; read off the True rows of the truth table, one conjunct per row.
• CNF ➔ AND of ORs; read off the False rows, negating each literal — the sign flip is the whole trick.
• [[CNF Encoding Patterns (At Least, At Most, Exactly)|At least $x$ from $n$]] ➔ clause size $m=n-x+1$, write all $\left(\genfrac{}{}{0ex}{}{n}{m}\right)$ clauses, literals unnegated.
• At most $y$ from $n$ ➔ same formula on negated literals with $x=n-y$, giving $m=y+1$ and $\left(\genfrac{}{}{0ex}{}{n}{m}\right)$ clauses.
• Exactly $z$ ➔ (at least $z$) $\wedge$ (at most $z$) · precondition both halves must be written; one alone is a strict inequality.
• Encoding a problem ➔ ① variable per atomic choice ② clauses per validity rule ③ conjoin · precondition the rules, not just the certificate, must be encoded.

3️⃣ Predicates and Quantifiers

• Predicate ➔ a proposition-valued function $P(x)$; a free variable makes it not yet a proposition, a bound one does.
• Pairing rule ➔ $\exists$ pairs with $\wedge$, $\forall$ pairs with $\Rightarrow$ · precondition — $\forall x(P(x)\wedge Q(x))$ over-claims and $\exists x(P(x)\Rightarrow Q(x))$ is vacuously true.
• Negation ➔ $\neg \forall xP\equiv \exists x\neg P$; $\neg \exists xP\equiv \forall x\neg P$.
• Order sensitivity ➔ $\forall x\exists yP(x,y)\not\equiv \exists y\forall xP(x,y)$; the second is strictly stronger · precondition swapping is only safe for like quantifiers.
• Distribution ➔ $\forall$ distributes over $\wedge$, $\exists$ over $\vee$; the mixed pairs do not.

4️⃣ Proof Craft

• Claim shape ➔ technique ➔ $\exists$: exhibit one witness · $\forall$: never by example · $\Rightarrow$: direct or contrapositive · “no such thing”: contradiction.
• Set equality ➔ $A=B$ by double inclusion $A\subseteq B$ and $B\subseteq A$; each inclusion starts “let $x\in A$“.
• Contrapositive ➔ $P\Rightarrow Q\equiv \neg Q\Rightarrow \neg P$; contradiction assumes $P\wedge \neg Q$ and derives absurdity (canonical: $\sqrt{2}\notin \mathbb{Q}$).
• Induction ➔ base case at the smallest relevant $n$, then $P(n)\Rightarrow P(n+1)$ · precondition the hypothesis must be the full statement for $n$, and the smallest step must be tested (the classic failure is $n=1\to 2$).
• Faulty-proof tells ➔ missing/ wrong base case · hypothesis assumed for $n+1$ · ex falso (a false premise proves anything) · example offered for a $\forall$ claim.
• Countability ➔ an explicit listing proves countable; diagonalisation proves $\{$languages over $\Sigma \}$ uncountable ⟹ some language has no description at all.

5️⃣ Regular Expressions and Finite Automata

• Regex ➔ built from $\varnothing ,\epsilon$, letters, $\cup$, concatenation, $\ast$ · precondition $R^{\ast }$ includes $\epsilon$, and ${\mathtt{ab}}^{\ast }\ne (\mathtt{ab}{)}^{\ast }$ — precedence is $\ast$ then concat then $\cup$.
• Finding one ➔ describe the shape of an accepted word, then verify on the shortest strings including $\epsilon$.
• DFA ➔ $(Q,\Sigma ,\delta ,q_0,F)$ with $\delta$ total and single-valued; accept iff the unique run ends in $F$.
• NFA ➔ $\delta$ may be multi-valued or missing, $\epsilon$-moves allowed; accept iff some path ends in $F$.
• Complement ➔ swap Final/non-Final · precondition DFA only — the same swap on an NFA is wrong, because “some path accepts” does not negate pointwise.
• Kleene’s Theorem ➔ regex $\equiv$ NFA $\equiv$ DFA; proved by the cycle regex $\to$ NFA $\to$ DFA $\to$ regex.
• [[Converting Regular Expressions to NFA|regex $\to$ NFA]] ➔ Thompson-style edge rewriting, one construction per operator.
• [[NFA to DFA (Subset Construction)|NFA $\to$ DFA]] ➔ states are sets of NFA states; start $=\epsilon$-closure of $q_0$; Final iff the set meets $F$ · cost up to $2^q$ states — this is why the construction is not polynomial (see §1️⃣2️⃣).
• [[FA to Regular Expression (GNFA State Elimination)|FA $\to$ regex]] ➔ GNFA state elimination; before deleting a state, relabel every ordered pair $(q_{\text{in}},q_{\text{out}})$ as $R_{\text{direct}}\cup \left(R_{\text{in}}{R}_{\text{loop}}^{\ast }{R}_{\text{out}}\right)$ · precondition missing a pair loses strings, and $R_{\text{direct}}$ must be kept in the union.

6️⃣ Limits of Regularity

• Minimisation ➔ seed two colours (Final / non-Final), split any class whose rows disagree on successor colours, iterate to fixpoint · precondition the DFA must be complete first.
• Lexing vocabulary ➔ pattern = the regex · token = the name · lexeme = the matched text; conflicts resolved by maximal munch, then first-listed rule.
• Closure ➔ regular languages are closed under $\overline{\cdot }$, $\cup$, $\cap$, concatenation, $\ast$ · note $\cap$ is obtained via De Morgan; subsets and supersets are NOT closed.
• Pumping Lemma ➔ $L$ infinite regular with an $N$-state FA ⟹ $\forall w\in L,|w|\ge N$, $\exists x,y,z$: $w=xyz$, $y\ne \epsilon$, $|x|+|y|\le N$, $\forall i\ge 0:x{y}^{i}z\in L$ · precondition infinite and regular; it is necessary, never sufficient.
• Non-regularity recipe ➔ assume regular with pumping length $N$ ➔ choose $w$ so that $|x|+|y|\le N$ forces $y$ into one block (canonically $w={\mathtt{a}}^N{\mathtt{b}}^N$) ➔ pump up or down ($i=0$ is legal) ➔ contradiction.
• Closure shortcut ➔ if $L\cap R$ is known non-regular for a regular $R$, then $L$ is non-regular (e.g. EQUAL $\cap {\mathtt{a}}^{\ast }{\mathtt{b}}^{\ast }$).

7️⃣ Context-Free Grammars and PDAs

• CFG ➔ terminals, nonterminals, productions $A\to \alpha$ with a single nonterminal on the left, start symbol $S$; a CFL is any language some CFG generates.
• Derivation ➔ leftmost and rightmost give the same tree and the same length; the prefix property is what makes leftmost usable for parsing.
• Grammar-writing stock ➔ ${\mathtt{a}}^n{\mathtt{b}}^n$: $S\to \mathtt{a}S\mathtt{b}\mid \epsilon$ · Dyck: $S\to \epsilon \mid (S)\mid SS$ · PALINDROME: $S\to \mathtt{a}S\mathtt{a}\mid \mathtt{b}S\mathtt{b}\mid \mathtt{a}\mid \mathtt{b}\mid \epsilon$.
• Regular grammar ➔ every rule has a semiword RHS; from an NFA, $X\stackrel{z}{\to }Y$ becomes $X\to zY$ ⟹ $\{$regular$\}⊊\{$CFL$\}$.
• PDA ➔ NFA + stack; transition $x,y\to z$ = read $x$, pop $y$, push $z$; $$$ marks the stack bottom; accept iff some path reaches a Final state.
• Equivalence ➔ CFG $⟺$ PDA (both directions constructive); an NFA is a stackless PDA · precondition deterministic PDAs are strictly weaker — $\text{DCFL}⊊\text{CFL}$.

8️⃣ Parsing, Chomsky Normal Form, CYK

• Shift-reduce ➔ stack + buffer; shift moves one token across, reduce applies a rule in reverse; accept iff stack $=S$ and buffer empty.
• Conflicts ➔ shift-reduce (both legal) and reduce-reduce (two rules match) both signal grammar ambiguity.
• Toolchain ➔ Lex $\to$ lex.yy.c / yylex(); Yacc $\to$ y.tab.c / yyparse(); defaults resolve shift-reduce by shifting and reduce-reduce by the first-listed rule.
• Chomsky NF ➔ every rule $A\to BC$ (live) or $A\to \mathtt{z}$ (dead) · precondition CNF generates the non-empty words only; $\epsilon$ goes to the nullability algorithm. ⚠ not Conjunctive Normal Form.
• 5-step conversion ➔ ① eliminate $\epsilon$-productions (to fixpoint) ② eliminate unit productions ③ isolate terminals into dead rules ④ break long RHS into binary chains ⑤ tidy unreachable/dead nonterminals.
• CYK ➔ fill by increasing substring length; length-$\ell$ cell takes the union over the $\ell -1$ binary splits; Accept iff $S$ appears in the whole-string cell · precondition grammar in Chomsky NF · cost $O(n^3)$.
• CFL Pumping Lemma ➔ CFG in CNF with $k$ nonterminals ⟹ $\forall w\in L$ with $|w|>2^{k-1}$, $\exists u,v,x,y,z$: $w=uvxyz$, $vy\ne \epsilon$, $|vxy|\le 2^k$, $\forall i\ge 0:u{v}^{i}x{y}^{i}z\in L$ · note CNF enters via the binary-tree height argument.
• Non-CF recipe ➔ take $w={\mathtt{a}}^N{\mathtt{b}}^N{\mathtt{a}}^N$ or ${\mathtt{a}}^N{\mathtt{b}}^N{\mathtt{c}}^N$ ➔ case-split on which blocks $v,y$ occupy ➔ $|vxy|\le 2^k$ stops them spanning all three blocks ⟹ pumping breaks the counts.

9️⃣ Turing Machines

• TM ➔ two-way infinite tape, head, finite program; Start $=1$, Accept $=2$; a crash (no applicable transition) rejects.
• Three outcomes ➔ ${\Sigma }^{\ast }$ partitions into $\text{Accept}(T)$, $\text{Reject}(T)$, $\text{Loop}(T)$ · definition $T$ is a decider iff $\text{Loop}(T)=\varnothing$.
• FA $\to$ TM ➔ 5-step conversion ⟹ every regular language is decidable.
• Building recipe ➔ mark-and-sweep: mark leftmost unmarked $\mathtt{a}$, run right to the matching $\mathtt{b}$, mark, return, repeat; accept when a full sweep finds nothing left to match.
• Unary code ➔ $n\mapsto {\mathtt{a}}^n$, tuples separated by $\mathtt{b}$; $f$ is computable iff some TM leaves $f(x)$ on the tape · precondition the Church–Turing thesis is a thesis, not a theorem — it cannot be cited as a proof step.
• Code words ➔ one row per transition, 5 fields: state ${\mathtt{a}}^n\mathtt{b}$, 2-letter symbols, 1-letter direction; $\text{CWL}=({\mathtt{aa}}^{\ast }\mathtt{ba}{\mathtt{a}}^{\ast }\mathtt{b}(\mathtt{a}\cup \mathtt{b}{)}^5{)}^{\ast }$ is regular but strictly larger than the set of genuine TM codes.
• UTM ➔ takes \langle M\rangle\,\texttt{\},x$andsimulates$M$on$x$ — programs as data, the stored-program idea.

🔟 Decidability and Mapping Reductions

• Decidable ➔ $L=\text{Accept}(M)$ for some decider $M$; then $\overline{L}=\text{Reject}(M)$ comes free. Synonyms: recursive, solvable.
• Problem $\leftrightarrow$ language ➔ a decision problem becomes the language of its YES-inputs; objects encode as $⟨O⟩$, tuples as $⟨O_1,\dots ,O_n⟩$.
• Closure ➔ decidable languages are closed under $\overline{\cdot },\cup ,\cap$, concatenation — proved by running deciders as subroutines · precondition subroutine calls must be shown to terminate, which is exactly what a decider guarantees.
• FA-Empty ➔ mark the Start state, propagate forward along transitions to fixpoint; Accept iff no Final state is marked.
• CFG-Empty ➔ mark terminals, propagate upward through rules to fixpoint; Accept iff $S$ is UNmarked.
• RegExpEquiv ➔ decide emptiness of $(L(A)\cap \overline{L(B)})\cup (\overline{L(A)}\cap L(B))$ · cost requires determinisation, so decidable but not polynomial.
• Mapping reduction ➔ computable total $f$ with $x\in K⟺f(x)\in L$, written $K{\le }_{m}L$ · precondition the certifying iff chain must be written both ways.
• Transfer ➔ $L$ decidable $\Rightarrow K$ decidable; $K$ undecidable $\Rightarrow L$ undecidable · precondition ${\le }_m$ is reflexive and transitive, not symmetric — direction is everything.
• Degenerate case ➔ reducing from a decidable $K$ proves nothing about $L$, and needs $L\ne \varnothing ,{\Sigma }^{\ast }$ to exist at all.

1️⃣1️⃣ Undecidability and Recursive Enumerability

• Existence argument ➔ TMs are countable, languages are uncountable ⟹ undecidable languages exist · limitation names none of them.
• HALT ➔ $\{⟨P,x⟩:P$ halts on $x\}$ is undecidable; proof builds $E$ that flips the diagonal, so the assumed decider cannot exist.
• Input-blind gadget ➔ from $M$ build $M^{\prime }$ = “ignore the input, run $M$ on $⟨M⟩$” ⟹ HALT-FOR-ZERO, ALWAYS HALTS, SOMETIMES HALTS all undecidable.
• NEVER HALTS ➔ obtained by the Accept/Reject swap · precondition the swap is illegal on recognisers (a loop is neither), legal only on deciders.
• Decidable side ➔ bounded-step halting and state-counting are decidable; acceptance and $\exists$-input halting are not.
• r.e. ➔ $L=\text{Accept}(T)$ with $\text{Loop}(T)$ unrestricted; synonyms Turing-recognisable, type 0.
• Bridge theorem ➔ $L$ decidable $⟺$ $L$ and $\overline{L}$ are both r.e. — proved by interleaving both machines one step at a time.
• Separation ➔ $\text{HALT}$ is r.e. but undecidable; $\overline{\text{HALT}}$ is not r.e.; decidable $=$ r.e. $\cap$ co-r.e.
• Enumeration ➔ $L$ r.e. $⟺$ $L$ is enumerated by some machine, using the $k$-then-$i$ dovetailing schedule · precondition a naive “run input 1 to completion first” schedule fails on a looping input.

1️⃣2️⃣ P, NP and Polynomial-Time Reductions

• Running time ➔ $t_M(n)=\max \{t_M(x):|x|=n\}$ · precondition $M$ must be a decider, else the max is undefined.
• $\mathrm{P}$ ➔ languages with an $O(n^k)$ decider, $k$ fixed — $n^{\log n}$ does not qualify. Placement: regular $⊊$ CFL $⊊\mathrm{P}⊊$ decidable.
• Model independence ➔ reasonable machine models simulate each other with polynomial slowdown, and a polynomial of a polynomial is a polynomial.
• Verifier & certificate ➔ $L\in \mathrm{NP}$ iff some polynomial-time $V$ has $x\in L⟺\exists y:V(x,y)$ accepts · precondition the time bound is in $|x|$, never $|y|$.
• 4-part membership proof ➔ ① state the certificate ② state the verifier ③ prove the iff ④ bound the time. All four are marked.
• Inclusions ➔ $\mathrm{P}\subseteq \mathrm{NP}$ (ignore the certificate) and $\mathrm{NP}\subseteq \mathrm{EXP}$ (search $\le 2^{c{n}^k}$ certificates).
• NDTM ➔ $\mathrm{NP}$ = languages decided by a nondeterministic TM in polynomial time · precondition the DFA $=$ NFA equivalence does not transfer — determinising costs exponential time here, not just states.
• Instance stock ➔ VERTEX COVER ($\le k$) · INDEPENDENT SET, CLIQUE ($\ge k$) · SAT / 2-SAT / 3-SAT · $k$-COLOURABILITY · HAMILTONIAN CIRCUIT · PARTITION · SUBSET SUM · GRAPH ISOMORPHISM.
• [[Polynomial-Time Reductions|${\le }_P$]] ➔ ${\le }_m$ with $f$ computable in $O(n^k)$; three marked parts: function · iff chain · time bound.
• Output-length lemma ➔ a TM emits $\le 1$ symbol per step ⟹ $f$ in time $O(n^k)$ forces $|f(x)|=O(n^k)$ · precondition this is the step that makes composition work; omitting it is the standard deduction.
• Transfer ➔ $L\in \mathrm{P}\Rightarrow K\in \mathrm{P}$; $K\notin \mathrm{P}\Rightarrow L\notin \mathrm{P}$ · precondition every old ${\le }_m$ construction must be re-timed — $\text{RegExpEquiv}{\le }_m\text{FA-Empty}$ is not ${\le }_P$.
• Reduction stock ➔ $\text{IS}{\le }_P\text{CLIQUE}$: $f(G,k)=(\overline{G},k)$ · $\text{VC}{\le }_P\text{IS}$: $f(G,k)=(G,n-k)$ · $\text{PARTITION}{\le }_P\text{SUBSET SUM}$: target $=\frac{1}{2}\sum s_i$.

1️⃣3️⃣ NP-Completeness

• Definition ➔ $L$ is NP-complete iff (a) $L\in \mathrm{NP}$ and (b) $\forall K\in \mathrm{NP}:K{\le }_{P}L$ · precondition (b) alone is only NP-hard.
• Master theorem ➔ an NP-complete $L$ has a polynomial-time decider $⟺\mathrm{P}=\mathrm{NP}$; ($\Leftarrow$) spends condition (a), ($\Rightarrow$) spends (b) plus the ${\le }_P$ transfer theorem.
• Equivalence class ➔ for NP-complete $L$: $K\in \mathrm{NP}⟺K{\le }_{P}L$, and $K$ is NP-complete $⟺K{\le }_{P}L\wedge L{\le }_{P}K$.
• Cook-Levin Theorem ➔ SATISFIABILITY (satisfiable CNF expressions) is NP-complete · note the proof is non-examinable; part (a) — certificate = truth assignment, verify clause-by-clause — is not.
• Encoding recipe ➔ ① variables for the certificate ② auxiliary variables ③ rules $\to$ CNF via the at-least / at-most templates of §2️⃣ ④ state as an algorithm and count the clauses.
• PARTITION INTO TRIANGLES ${\le }_P$ SAT ➔ $x_{T_i}$ per triangle; per vertex one at-least-one clause and $\neg x_{T_i}\vee \neg x_{T_j}$ per triangle pair at it · cost $O(n^3)$ variables, $O(n^5)$ clauses.
• Inheritance theorem ➔ $K$ NP-complete $\wedge L\in \mathrm{NP}\wedge K{\le }_{P}L\Rightarrow L$ NP-complete · precondition the reduction runs from the known-hard language; $L{\le }_{P}K$ proves nothing.
• $\text{SAT}{\le }_{P}3\text{-SAT}$ ➔ pad clauses of size $<3$ with fresh $w_i$ in all sign patterns; chain clauses of size $>3$ with fresh $z_j$ links $(\cdots \vee z_j)\wedge (\neg z_j\vee \dots )$.
• $3\text{-SAT}{\le }_P\text{VERTEX COVER}$ ➔ variable-edge $(x_i,\neg x_i)$ per variable, triangle per clause, connector edge from each clause position to its literal; $k_{\varphi }=2m+n$ · precondition $k_{\varphi }$ must be the exact minimum, else the correspondence breaks.
• Chain ➔ $\text{SAT}{\le }_{P}3\text{-SAT}{\le }_P\text{VC}{\le }_P\text{IS}{\le }_P\text{CLIQUE}$ ⟹ all five NP-complete.
• Living with it ➔ drop exactly one of efficient · deterministic · all-cases · exact ⟹ exponential exact / randomised / special-case / approximation algorithm.
• co-NP ➔ complements of $\mathrm{NP}$ languages; $\mathrm{P}\subseteq \mathrm{NP}\cap \text{co-}\mathrm{NP}$, and whether that inclusion is equality is open.

🪜 The ladder, in one line

$$\text{regular}⊊\text{context-free}⊊\mathrm{P}⊊\text{decidable}⊊\text{r.e.}⊊\text{all languages},\mathrm{P}\subseteq \mathrm{NP}\subseteq \mathrm{EXP}$$

• Named separating inhabitants ➔ ${\mathtt{a}}^n{\mathtt{b}}^n$ (not regular) · ${\mathtt{a}}^n{\mathtt{b}}^n{\mathtt{a}}^n$ (not context-free, still decidable) · $\text{HALT}$ (r.e., not decidable) · $\overline{\text{HALT}}$ (not r.e.).
• The unproved links ➔ every $⊊$ in the first chain is a theorem with a witness above; the second chain’s $\subseteq$ signs are not known to be strict — $\mathrm{P}\stackrel{?}{=}\mathrm{NP}$ is the open question, and $\mathrm{NP}$ straddles the $\mathrm{P}$/decidable frontier rather than sitting in a tier of its own.