Deterministic Finite Automata

DFAs

To start this discussion off, it is important to understand Finite Automata and specifically Nondeterministic Finite Automata. Upon closer look, we can see an immediate relation between NFAs and DFAs: they are equivalent in expressive power. By this, I mean that anything a DFA can represent, an NFA can also represent. This also must mean that any DFA can simulate an NFA, which is a key to converting an NFA to a DFA.

The idea behind this is simple. For every possible NFA configuration, supposing there are $N$ states, then there are $2^N$ subsets and thus all that needs to be done is to create a DFA with a state for each valid configuration in the NFA. This would still run as a function of input length, but it may face a space complexity problem in an implementation, more on this later. For now, the process of turning an NFA into a DFA is known as NFA Subset Construction.