The whole Theory of Computation formula sheet, to print

Valid only for a complete DFA. Swapping the accepting states of an NFA does not in general complement its language.

Run complete DFAs with $m$ and $n$ states together; states are pairs. Accept when both components accept (intersection), at least one accepts (union), the first accepts and the second does not (difference), or exactly one accepts (symmetric difference).

For a fixed set of $n$ labelled states, a fixed start state and an alphabet of $k$ symbols: each of the $nk$ transitions has $n$ choices, and $F$ is any of the $2^n$ subsets of $Q$. This counts machines, not languages; many machines accept the same language. Example: $n=2$, $k=2$ gives $2^4\cdot 2^2=64$.

Same states and start state. Each new edge stands for '$\epsilon$-moves, then $a$, then $\epsilon$-moves'; a state becomes accepting if an accepting state can be reached from it by $\epsilon$-moves alone.

The bound is tight: the language 'the $n$-th symbol from the right is 1' has an $(n+1)$-state NFA whose minimal DFA has $2^n$ states. Often far fewer subsets are reachable.

Each class of prefixes is one state. $L$ is regular exactly when there are finitely many classes.

Union is commutative and associative; concatenation is associative but not commutative.

$r^{+}$ means one or more repetitions.

All five denote the strings formed by any mixture of $r$-strings and $s$-strings. $(r+s{)}^{\ast }$ is NOT equal to $r^{\ast }+s^{\ast }$.

Both sides are $r$ followed by alternating $s$, $r$ blocks. $(rs{)}^{\ast }\ne (sr{)}^{\ast }$ in general.

Concatenation distributes over union on both sides; union does not distribute over concatenation ($r+st\ne (r+s)(r+t)$ in general).

When $\epsilon \notin L(P)$ the stated solution is the unique one. When $\epsilon \in L(P)$ it is still a solution (the smallest) but not the only one. The first form fits Arden's method below, where each equation lists the strings that reach a state.

Linear in the length of the expression. Each symbol ($a$, $\epsilon$ or $\varnothing$) and each union or star adds two states; concatenation adds none.

Holds for every input $w$ because both machines are deterministic and complete.

Applies to a total DFA only. If some transitions are missing, first add a dead (trap) state and send every missing transition to it. The complement DFA has the same states, so the minimal total DFAs of $L$ and $L^c$ have the same number of states. Swapping accepting states in an NFA does not complement it: convert the NFA to a DFA first (the subset construction can need up to $2^n$ states for an $n$-state NFA).

For total DFAs with $m$ and $n$ states, the product has $mn$ states. A pair is accepting when both components accept for intersection, when either accepts for union, and when the first accepts and the second does not for difference.

Here $\hat{\delta }$ is the extended transition function on strings, with $\hat{\delta }(q,\epsilon )=q$. The new DFA has the same states, start state and accepting states as the DFA for $L$, and it accepts $h^{-1}(L)=\{w:h(w)\in L\}$.

The implication runs one way only. A language can satisfy the conditions and still be non-regular, so the lemma can prove non-regularity but never regularity. For example, $\{a^i{b}^j{c}^k:i=0\text{ or }j=k\}$ satisfies the lemma with $p=1$ (pump the first symbol), yet it is not regular: its intersection with $a{b}^{\ast }{c}^{\ast }$ is $\{a{b}^n{c}^n:n\ge 0\}$. The pumping length $p$ can be taken as the number of states of any DFA for $L$.

Unlike the pumping lemma, this is an iff. The number of classes equals the number of states of the minimal total DFA for $L$, counting the dead state if the minimal total DFA has one.

For $|w|=n\ge 1$ and any derivation of $w$ from $S$ in a CNF grammar: $n-1$ steps use $A\to BC$ and $n$ steps use $A\to a$. In the parse tree there are $n-1$ variable nodes with two variable children and $n$ variable nodes whose only child is a terminal leaf, so $2n-1$ variable nodes, one per step.

For $|w|=n\ge 1$; each step adds exactly one terminal.

Every CFG has an equivalent NPDA and every NPDA has an equivalent CFG, with either acceptance mode.

Proved by running a PDA and a DFA together; the same holds for DCFLs. Hence $L-R=L\cap \overline{R}$ is a CFL, but $R-L$ need not be.

A necessary condition only: it can prove a language is not context-free, never that it is. If L is generated by a Chomsky normal form grammar with k variables, $p=2^k$ works.

Only accepted strings count; strings on which M loops or rejects are outside L(M).

Here the complement is taken with respect to ${\Sigma }^{\ast }$. To decide, run both recognisers in parallel (alternating steps); exactly one of them accepts: the one for $L$ if $w\in L$, the one for $\overline{L}$ otherwise.

Use the contrapositive: if $A{\le }_{m}B$ and $A$ is undecidable, $B$ is undecidable. Also: $A{\le }_{m}B$ and $B$ RE implies $A$ RE; $A{\le }_{m}B$ and $A$ not RE implies $B$ not RE. Since $A{\le }_{m}B$ if and only if $\overline{A}{\le }_m\overline{B}$, reducing $A_{TM}$ to $\overline{B}$ proves $B$ is not RE. Direction matters.

P is a property of the language L(M). Non-trivial: some TM languages have it and some do not. Semantic: it depends only on L(M), not on the machine's structure.