Theory of Computation formula sheet

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).

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.

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.

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.