A dirty little ditty on Finite Automata

This post builds on the previous post about Formal Languages.

Some Formal Definitions

A Deterministic Finite Automata (DFA) is

The DFA is then often referred to as the ordered quintuple \( A=(\mathcal{Q},\Sigma,\delta_F,q_0,F) \).

Defining how strings act on DFAs.

Given a DFA, \( A=(\mathcal{Q}, \Sigma, \delta, q_0, F) \), a state \( q_i\in\mathcal{Q} \), and a string \( w\in\Sigma^* \), we can define \( \delta(q_i,w) \) like so:

And in this way, we have defined how DFAs can interpret strings of symbols rather than just single symbols.

The language of a DFA

Given a DFA, \( A=(\mathcal{Q}, \Sigma, \delta, q_0, F) \), we can define “the language of \( A \)”, denoted \( L(A) \), as \( {w\in\Sigma^*|\delta(q_0,w)\in F} \).

Some Examples, Maybe?

Example 1:

Let’s construct a DFA that accepts only strings beginning with a 1 that, when interpreted as binary numbers, are multiples of 5. So some examples of strings that would be in \( L(A) \) are 101, 1010, 1111

Some More Formal Definitions

A Nondeterministic Finite Automata (NFA) is

The NFA is then often referred to as the ordered quintuple \( A=(\mathcal{Q},\Sigma,\delta_N,q_0,F) \).

Defining how strings act on NFAs.

Given an NFA, \( N=(\mathcal{Q}, \Sigma, \delta, q_0, F) \), a collection of states \( \mathcal{S}\subseteq\mathcal{Q} \), and a string \( w\in\Sigma^* \), we can define \( \delta(\mathcal{S},w) \) like so:

And in this way, we have defined how NFAs can interpret strings of symbols rather than just single symbols.

Maybe in another post, we’ll get past the definitions! :-/