Back to formula hub
FORMULA SHEET

Theory of Computation

DFA states

2^n subset construction

NFA to DFA worst case.

CFG ambiguity

multiple parse trees

One string with two leftmost derivations is enough.

Closure

Regular closed under complement

Also closed under union, intersection, and difference.