Nondeterministic Finite Automata

NFAs

In the context of Regular Expressions, the empty string $\varepsilon$ is considered to be a valid RE. A great use-case of the empty string is to construct Finite Automata representations from REs via an $\varepsilon$-transition. However, a state that can take an empty string transition must be able to take multiple transactions per character. Thus, the idea of a Nondeterministic FA is pretty intuitive, given that it describes an FA where the transition function can be multivalued and may contain $\varepsilon$-transitions. This, naturally, gives way to its counterpartAnd more relevant piece of theory, the Deterministic Finite Automata.

NFA Rules

Throughout the years, two distinct models have been developed to reason about the behavior of NFAs. Both of these center on the actions an NFA should take given a nondeterministic state.

1. Every time the NFA must make a nondeterministic choice, it follows the transition that leads to an accepting state for the input string. Essentially, it just guesses the right path
2. Each time the NFA must make a nondeterministic choice, the NFA clones itself to pursue each possible transition. The more practical, concurrent approach.

More

Applying this theory into practice is perhaps the most valuable and important part of this whole thing. Generally, in the context of Scanners, the flow goes from RE, to NFA, to DFA. Thompson's Contstruction is the first step.