A dirty little ditty on Finite Automata

Some Formal Definitions

A Deterministic Finite Automata (DFA) is

  • A set \mathcal{Q} called “states”
  • A set \Sigma called “symbols”
  • A function \delta_F:\mathcal{Q}\times\Sigma \to \mathcal{Q}
  • A designated state q_0\in\mathcal{Q} called the start point
  • A subset F\subseteq\mathcal{Q} called the “accepting states”.

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:

  • If w only has one symbol, we can consider w to be the symbol and define \delta(q_i,w) to be the same as if we considered w as the symbol.
  • If w=xv, where x\in\Sigma and v\in\Sigma^*, then \delta(q_i, w)=\delta(\delta(q_i,x),v).

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

  • A set \mathcal{Q} called “states”
  • A set \Sigma called “symbols”
  • A function \delta_N:\mathcal{Q}\times\Sigma \to \mathcal{P}\left(\mathcal{Q}\right)
  • A designated state q_0\in\mathcal{Q} called the start point
  • A subset F\subseteq\mathcal{Q} called the “accepting states”.

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:

  • If w only has one symbol, then we can consider w to be the symbol and define \delta(\mathcal{S},w):=\bigcup\limits_{s\in\mathcal{S}}\delta(s,w).
  • If w=xv, where x\in\Sigma and v\in\Sigma^*, then \delta(\mathcal{S}, w)=\bigcup\limits_{s\in\mathcal{S}}\delta(\delta(s,x),v).

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! :-/

Advertisements
A dirty little ditty on Finite Automata

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s