FIT2014 Unit Cheatsheet

Context: FIT2014_MOC · the WHOLE unit in one re-read — languages → logic → automata → grammars → parsing → Turing machines → decidability → complexity → NP-completeness. Links for depth only. Read order: ⛔ = firing precondition (where marks die) · ⚙️ Procedure boxes = execute by hand · 🧮 Blueprint boxes = proof skeleton to fill in · Route: Mid-sem ⟵ §1–§8 · A1 ⟵ §5 · A2 ⟵ §6 lexing, §8 parsing, §9–§11 · Exam ⟵ all.

Quick Revision

• 🎯 Objective: classify the question — construct/execute (run a ⚙️ procedure) or prove (fill a 🧮 blueprint) — then place the language on the ladder below.
• ⚡ Key Constraint: hypothesis discipline — infinite vs finite, regular vs context-free, decidable vs recognisable, ${\le }_m$ vs ${\le }_P$; a rule fired without its precondition scores nothing.

🪜 The Ladder — the Whole Unit on One Screen

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

Class	Machine	Generator	Prove NOT in it	Witness just outside
Regular	DFA $\equiv$ NFA	regex · regular grammar	pumping lemma or closure shortcut (§6)	${\mathtt{a}}^n{\mathtt{b}}^n$
Context-free	PDA (nondeterministic)	CFG	CFL pumping lemma (§8)	${\mathtt{a}}^n{\mathtt{b}}^n{\mathtt{a}}^n$
$\mathrm{P}$	$O(n^k)$ decider	—	—	—
Decidable	decider TM, $\text{Loop}=\varnothing$	—	reduce from an undecidable language (§11)	$\text{HALT}$
r.e. (type 0)	recogniser TM · enumerator	—	show $\overline{L}$ r.e. but $L$ undecidable	$\overline{\text{HALT}}$
All languages	—	—	uncountably many, TMs countable	—

• Proved vs open ➔ every $⊊$ in the first chain is a theorem with a witness above · the $\subseteq$ signs in the second chain are not known strict — $\mathrm{P}\stackrel{?}{=}\mathrm{NP}$ is open · $\mathrm{NP}$ straddles the $\mathrm{P}$/decidable frontier, not a tier of its own.

1️⃣ Languages and Words (W1)

• Alphabet & word ➔ $\Sigma$ finite non-empty · word $=$ finite sequence over $\Sigma$ · $\epsilon$ empty word · ⛔ $\varnothing \ne \{\epsilon \}$ — no words vs one word.
• Closure ➔ ${\Sigma }^{\ast }=$ all finite words incl. $\epsilon$ · $x^0=\epsilon$ · ${\Sigma }^{\ast }$ is countably infinite for finite $\Sigma$.
• Language ➔ any $L\subseteq {\Sigma }^{\ast }$ · ⛔ state the defining predicate, never membership by intuition.
• 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 (W1)

• Connectives ➔ $\neg ,\wedge ,\vee ,\Rightarrow ,\iff$ · $A\Rightarrow B\equiv \neg A\vee B$ · ⛔ eliminate implications 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$ · $n$ terms by induction, not assertion.

From a truth table	Shape	Read off	One term per row	Literals
DNF	OR of ANDs	True rows	conjunct	as in the row
CNF	AND of ORs	False rows	clause	negated — the whole trick

Constraint on $n$ variables	Clause size $m$	Clauses	Literals
at least $x$ true	$n-x+1$	all $\left(\genfrac{}{}{0ex}{}{n}{m}\right)$	unnegated
at most $y$ true	$y+1$	all $\left(\genfrac{}{}{0ex}{}{n}{m}\right)$	negated (at-least $n-y$ false)
exactly $z$	both rows above	sum	⛔ write both halves

🧮 Blueprint — encode a problem in CNF

① one variable per atomic choice ② clauses per validity rule ③ conjoin · ⛔ encode the rules, not just the certificate.

3️⃣ Predicates and Quantifiers (W1)

• Predicate ➔ proposition-valued $P(x)$ · a free variable leaves it not yet a proposition; bound makes it one.
• Pairing rule ➔ $\exists$ with $\wedge$, $\forall$ with $\Rightarrow$ · ⛔ $\forall x(P\wedge Q)$ over-claims; $\exists x(P\Rightarrow Q)$ is vacuously true.
• Negation ➔ $\neg \forall xP\equiv \exists x\neg P$ · $\neg \exists xP\equiv \forall x\neg P$.
• Order matters ➔ $\forall x\exists yP\not\equiv \exists y\forall xP$ (the second is stronger) · ⛔ swap only like quantifiers.
• Distribution ➔ $\forall$ over $\wedge$, $\exists$ over $\vee$ · the mixed pairs do not distribute.

4️⃣ Proof Craft (W2)

Claim shape	Technique
$\exists xP(x)$	exhibit one witness
$\forall xP(x)$	general argument — never by example
$P\Rightarrow Q$	direct, or contrapositive $\neg Q\Rightarrow \neg P$
“no such thing exists”	contradiction: assume $P\wedge \neg Q$, derive absurdity ($\sqrt{2}\notin \mathbb{Q}$)
$A=B$ (sets)	double inclusion $A\subseteq B$, $B\subseteq A$, each from “let $x\in A$“
$\forall n\ge n_0$	induction
countable	an explicit listing
uncountable	diagonalisation — e.g. languages over $\Sigma$ ⟹ some language has no description

• Induction ➔ base at the smallest relevant $n$, then $P(n)\Rightarrow P(n+1)$ · ⛔ hypothesis is the full statement for $n$; test the smallest step ($n=1\to 2$ is the classic failure).
• Faulty-proof tells ➔ missing/wrong base · hypothesis assumed for $n+1$ · ex falso (false premise proves anything) · example offered for a $\forall$.

5️⃣ Regular Expressions and Finite Automata (W2–W3 · A1)

• Regex ➔ $\varnothing ,\epsilon$, letters, $\cup$, concatenation, $\ast$ · precedence $\ast$ › concat › $\cup$ · ⛔ $R^{\ast }\ni \epsilon$ and ${\mathtt{ab}}^{\ast }\ne (\mathtt{ab}{)}^{\ast }$.
• Finding one ➔ describe the shape of an accepted word, then test the shortest strings incl. $\epsilon$.

Automaton	$\delta$	$\epsilon$-moves	Accepts iff	Complement by swapping Final?
DFA $(Q,\Sigma ,\delta ,q_0,F)$	total, single-valued	no	the unique run ends in $F$	yes
NFA	multi-valued or missing	yes	some path ends in $F$	⛔ no — “some path” doesn’t negate pointwise

• Kleene’s Theorem ➔ regex $\equiv$ NFA $\equiv$ DFA, proved by the cycle regex → NFA → DFA → regex.

⚙️ Procedure — the Kleene cycle

• regex → NFA ➔ Thompson-style edge rewriting, one construction per operator.
• NFA → 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 ⟹ not polynomial (§1️⃣2️⃣).
• FA → regex ➔ GNFA state elimination: before deleting a state, relabel every ordered pair $(q_{\text{in}},q_{\text{out}})$ as $R_{\text{direct}}\cup R_{\text{in}}{R}_{\text{loop}}^{\ast }{R}_{\text{out}}$ · ⛔ a missed pair loses strings; keep $R_{\text{direct}}$ in the union.

6️⃣ Limits of Regularity (W4)

⚙️ Procedure — minimise a DFA

⛔ complete the DFA first · ① two colours: Final / non-Final ② split any class whose rows disagree on successor colours ③ iterate to fixpoint.

• Lexing vocabulary (A2) ➔ pattern $=$ the regex · token $=$ the name · lexeme $=$ the matched text · conflicts: maximal munch, then first-listed rule.
• Closure ➔ closed under complement, $\cup$, $\cap$ (via De Morgan), concatenation, $\ast$ · ⛔ subsets and supersets are not closed.
• Pumping lemma ➔ $L$ infinite regular, $N$-state FA ⟹ every $w\in L$ with $|w|\ge N$ splits $w=xyz$: $y\ne \epsilon$, $|xy|\le N$, $x{y}^{i}z\in L\forall i\ge 0$ · ⛔ infinite and regular; necessary, never sufficient.

🧮 Blueprint — prove $L$ non-regular

① assume regular, pumping length $N$ ② choose $w$ so $|xy|\le N$ forces $y$ into one block (canonical ${\mathtt{a}}^N{\mathtt{b}}^N$) ③ pump up or down ($i=0$ is legal) ④ contradiction. Shortcut: $L\cap R$ non-regular for a regular $R$ ⟹ $L$ non-regular (EQUAL $\cap {\mathtt{a}}^{\ast }{\mathtt{b}}^{\ast }$).

7️⃣ Context-Free Grammars and PDAs (W5)

• CFG ➔ terminals, nonterminals, rules $A\to \alpha$ with one nonterminal on the left, start $S$ · CFL $=$ language of some CFG.
• Derivations ➔ leftmost and rightmost give the same tree and length · the prefix property makes leftmost usable for parsing.

Language	Grammar
${\mathtt{a}}^n{\mathtt{b}}^n$	$S\to \mathtt{a}S\mathtt{b}\mid \epsilon$
Dyck (balanced brackets)	$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$
any regular language	regular grammar: NFA edge $X\stackrel{z}{\to }Y$ ⟹ $X\to zY$ (semiword RHS) ⟹ regular $⊊$ CFL

• PDA ➔ NFA $+$ stack · $x,y\to z$ $=$ read $x$, pop $y$, push $z$ · \texttt{\}$ marks the bottom · accepts iff some path reaches Final.
• Equivalence ➔ CFG $⟺$ PDA, both directions constructive · an NFA is a stackless PDA · ⛔ deterministic PDAs are strictly weaker: $\text{DCFL}⊊\text{CFL}$.

8️⃣ Parsing, Chomsky Normal Form, CYK (W6 · A2)

• Shift-reduce ➔ stack $+$ buffer · shift moves a 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 ambiguity.

Tool	Emits	Entry point	Default conflict resolution
Lex	lex.yy.c	yylex()	maximal munch, then first-listed rule (§6)
Yacc	y.tab.c	yyparse()	shift-reduce ⟹ shift · reduce-reduce ⟹ first-listed rule

• Chomsky NF ➔ every rule $A\to BC$ (live) or $A\to \mathtt{z}$ (dead) · ⛔ generates non-empty words only — $\epsilon$ goes to the nullability algorithm · ⚠ not Conjunctive Normal Form.

⚙️ Procedure — CFG → Chomsky NF, then CYK

• Convert ➔ ① remove $\epsilon$-productions (to fixpoint) ② remove unit productions ③ isolate terminals into dead rules ④ break long RHS into binary chains ⑤ drop unreachable/dead nonterminals.
• CYK ➔ fill by increasing substring length; a length-$\ell$ cell is the union over its $\ell -1$ binary splits · accept iff $S$ is in the whole-string cell · ⛔ grammar in Chomsky NF · $O(n^3)$.

CFL pumping — what changes from §6	Regular	Context-free
Hypothesis	$N$-state FA	CFG in Chomsky NF, $k$ nonterminals
Long word	$|w|\ge N$	$|w|>2^{k-1}$
Split	$xyz$	$uvxyz$
Non-empty part	$y\ne \epsilon$	$vy\ne \epsilon$
Window	$|xy|\le N$	$|vxy|\le 2^k$ (binary-tree height)
Pump	$x{y}^{i}z$	$u{v}^{i}x{y}^{i}z$, $i\ge 0$

🧮 Blueprint — prove $L$ non-context-free

① 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 in every case.

9️⃣ Turing Machines (W7 · A2)

• TM ➔ two-way infinite tape, head, finite program · Start $=1$, Accept $=2$ · a crash (no applicable transition) rejects.
• Three outcomes ➔ ${\Sigma }^{\ast }=\text{Accept}(T)\cup \text{Reject}(T)\cup \text{Loop}(T)$ · $T$ is a decider iff $\text{Loop}(T)=\varnothing$.
• FA → TM ➔ 5-step conversion ⟹ every regular language is decidable.
• Mark-and-sweep ➔ mark the leftmost unmarked $\mathtt{a}$, run right to its matching $\mathtt{b}$, mark, return, repeat · accept when a sweep finds nothing left.
• Computable function ➔ unary $n\mapsto {\mathtt{a}}^n$, tuples split by $\mathtt{b}$; $f$ computable iff some TM leaves $f(x)$ on the tape · ⛔ Church–Turing is a thesis, never 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 larger than the set of genuine codes.
• UTM ➔ input \langle M\rangle\,\texttt{\},x$,simulates$M$on$x$ — programs as data.

🔟 Decidability and Mapping Reductions (W8 · A2)

• Decidable (recursive, solvable) ➔ $L=\text{Accept}(M)$ for a decider $M$; $\overline{L}=\text{Reject}(M)$ comes free.
• Problem ↔ language ➔ the YES-inputs · objects encoded $⟨O⟩$, tuples $⟨O_1,\dots ,O_n⟩$.
• Closure ➔ decidable languages closed under complement, $\cup$, $\cap$, concatenation — deciders as subroutines · ⛔ show every call terminates (a decider guarantees it).

⚙️ Procedure — emptiness and equivalence deciders

• FA-Empty ➔ mark Start, 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))$ · needs determinisation ⟹ decidable, not polynomial.

• Mapping reduction $K{\le }_{m}L$ ➔ computable total $f$ with $x\in K⟺f(x)\in L$ · ⛔ write the iff chain both ways.
• Transfer ➔ $L$ decidable ⟹ $K$ decidable · $K$ undecidable ⟹ $L$ undecidable · ⛔ 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.

1️⃣1️⃣ Undecidability and Recursive Enumerability (W9 · A2)

• Existence ➔ TMs countable, languages uncountable ⟹ undecidable languages exist — but names none.
• HALT ➔ $\{⟨P,x⟩:P\text{ halts on }x\}$ undecidable · proof: build $E$ that flips the diagonal ⟹ the assumed decider can’t exist.

🧮 Blueprint — prove $L$ undecidable

① pick a known-undecidable $K$ (HALT) ② build $f$: from $M$ make $M^{\prime }=$ “ignore the input, run $M$ on $⟨M⟩$” (the input-blind gadget) ③ prove $x\in K⟺f(x)\in L$ ④ conclude by transfer (§🔟) · ⛔ reduce from $K$ to $L$.

Problem	Status	Why
HALT, HALT-FOR-ZERO, ALWAYS HALTS, SOMETIMES HALTS	undecidable	input-blind gadget
NEVER HALTS	undecidable	Accept/Reject swap · ⛔ legal on deciders only — illegal on recognisers (a loop is neither)
acceptance · $\exists$-input halting	undecidable	—
bounded-step halting · state-counting	decidable	—

• r.e. (Turing-recognisable, type 0) ➔ $L=\text{Accept}(T)$, $\text{Loop}(T)$ unrestricted.
• Bridge theorem ➔ $L$ decidable $⟺$ $L$ and $\overline{L}$ r.e. — interleave both machines one step at a time ⟹ decidable $=$ r.e. $\cap$ co-r.e.
• Separation ➔ HALT r.e. but undecidable ⟹ $\overline{\text{HALT}}$ not r.e.
• Enumeration ➔ $L$ r.e. $⟺$ some machine enumerates it, via $k$-then-$i$ dovetailing · ⛔ “run input 1 to completion first” hangs on a looping input.

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

• Running time ➔ $t_M(n)=\max \{t_M(x):|x|=n\}$ · ⛔ $M$ must be a decider, else the max is undefined.
• $\mathrm{P}$ ➔ an $O(n^k)$ decider, $k$ fixed ($n^{\log n}$ fails) · reasonable models simulate each other with polynomial slowdown; poly of poly is poly.
• NP ➔ some poly-time $V$ with $x\in L⟺\exists y:V(x,y)$ accepts · ⛔ time bound in $|x|$, never $|y|$ · equivalently NDTM in poly time — ⛔ DFA $\equiv$ NFA does not transfer (determinising costs exponential time).
• Inclusions ➔ $\mathrm{P}\subseteq \mathrm{NP}$ (ignore the certificate) · $\mathrm{NP}\subseteq \mathrm{EXP}$ (search $\le 2^{c{n}^k}$ certificates).

🧮 Blueprint — prove $L\in \mathrm{NP}$ (all four parts are marked)

① state the certificate ② state the verifier ③ prove the iff ④ bound the time in $|x|$.

	Mapping ${\le }_m$	Poly-time ${\le }_P$
$f$ must be	computable, total	computable in $O(n^k)$
Marked parts	function · iff chain	function · iff chain · time bound
Transfers	decidability	membership in $\mathrm{P}$: $L\in \mathrm{P}\Rightarrow K\in \mathrm{P}$, $K\notin \mathrm{P}\Rightarrow L\notin \mathrm{P}$
⛔	direction	re-time old ${\le }_m$ proofs — $\text{RegExpEquiv}{\le }_m\text{FA-Empty}$ is not ${\le }_P$

• Output-length lemma ➔ a TM writes $\le 1$ symbol per step ⟹ $|f(x)|=O(n^k)$ — the step that makes composition work; omitting it is the standard deduction.
• 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.

Reduction	$f$
$\text{IS}{\le }_P\text{CLIQUE}$	$(G,k)\mapsto (\overline{G},k)$
$\text{VC}{\le }_P\text{IS}$	$(G,k)\mapsto (G,n-k)$
$\text{PARTITION}{\le }_P\text{SUBSET SUM}$	target $=\frac{1}{2}\sum s_i$

1️⃣3️⃣ NP-Completeness (W11)

• NP-complete ➔ (a) $L\in \mathrm{NP}$ and (b) $\forall K\in \mathrm{NP}:K{\le }_{P}L$ · ⛔ (b) alone is only NP-hard.
• Master theorem ➔ an NP-complete $L$ has a poly-time decider $⟺\mathrm{P}=\mathrm{NP}$ · ($\Leftarrow$) spends (a); ($\Rightarrow$) spends (b) $+$ ${\le }_P$ transfer.
• Equivalence class ➔ for NP-complete $L$: $K\in \mathrm{NP}⟺K{\le }_{P}L$ · $K$ NP-complete $⟺K{\le }_{P}L\wedge L{\le }_{P}K$.
• Cook-Levin Theorem ➔ SAT is NP-complete · proof non-examinable; part (a) — certificate $=$ truth assignment, check clause by clause — is examinable.

🧮 Blueprint — prove $L$ NP-complete

① $L\in \mathrm{NP}$ by the four-part proof (§1️⃣2️⃣) ② pick a known NP-complete $K$ ③ give $K{\le }_{P}L$: function · iff · time ④ conclude by inheritance · ⛔ reduce from the known-hard $K$; $L{\le }_{P}K$ proves nothing.

🧮 Blueprint — reduce a problem to SAT

① variables for the certificate ② auxiliary variables ③ rules → CNF via the §2️⃣ at-least / at-most table ④ state it as an algorithm and count the clauses.

Reduction	Construction	Size / catch
PARTITION INTO TRIANGLES ${\le }_P$ SAT	$x_{T_i}$ per triangle; per vertex an at-least-one clause $+$ $\neg x_{T_i}\vee \neg x_{T_j}$ per triangle pair at it	$O(n^3)$ variables, $O(n^5)$ clauses
$\text{SAT}{\le }_{P}3\text{-SAT}$	short clauses: pad with fresh $w_i$ in all sign patterns · long clauses: chain with fresh $z_j$, $(\cdots \vee z_j)\wedge (\neg z_j\vee \dots )$	fresh variables per clause
$3\text{-SAT}{\le }_P\text{VERTEX COVER}$	edge $(x_i,\neg x_i)$ per variable · triangle per clause · connector from each clause position to its literal · $k_{\varphi }=2m+n$	⛔ $k_{\varphi }$ must be the exact minimum

• 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.
• co-NP ➔ complements of $\mathrm{NP}$ languages · $\mathrm{P}\subseteq \mathrm{NP}\cap \text{co-}\mathrm{NP}$; whether it’s equality is open.