Finite Automata

Overview

Finite automata is a branch of automata used heavily in compilers. The idea is to formalize a representation for Recognizers in a way that can be programmed in then be used in the scanning process. Formally, FAs consist of a finite amount of states $S$, an alphabet $\sum$, a transition function $\delta(s,c)$, a start state $s_0$, and a set of accepting states $S_A$. The idea is that an FA accepts a string x if and only if, beginning at the start state, the sequence of characters in x terminate in an accepting state. Formally:

Of course, input is not always meant to be expected. In the context of programming, a keyword may be misspelled, or there may be some other syntax error. In this case, the transition function would map to an error state $S_e$. From a programming perspective, the pseudocode here is relatively simple:

state <- S0
char <- NextChar()

while (state != SE and char != eof) do
	state <- transitionFunction(state, char)
	char <- NextChar()
end

if (state is an accepting state) then
	success
else
	failure

FA as Recognizer Specs

As stated at the beginning of the note, finite automata is typically leveraged as a specification tool for recognizers. However, what we have learned thus far is not necessarily enough to complete this mapping yet. We are missing a concrete way to specify structure of words. While conceptually we have everything we need, we are missing a tool: Regular Expressions.