Finite Automata

A deterministic finite automaton (DFA, plural automata) is a finite state machine for the express purpose of determining whether a string (word) is in a language.

The set of words that the diagram describes the language .

$$\Sigma = \{ a, b \}, L = \text{the set of all words with an odd number of a's}$$

$$\Sigma = \{ a, b \}, L = \{ \varepsilon \}$$

A DFA is a 5-tuple (like a "DFA Space")

• is a finite alphabet (input symbols)
• is a finite set of states
• is the start state
• is the set of accepting states
• : is the transition function (current state some symbol in the alphabet new state)

Example from the odd number of a's DFA:

• : interpretation in Predicate Logic#Semantics (woo!)

The error state (nicknamed the dungeon state) is a non-accepting state that does now allow you to leave.

Drawing the implicit error state from the first example:

where is a sequence of symbols (as opposed to just 1 symbol)

A word is accepted by the DFA (that is, in the language specified by the DFA) if

Given a word, to check if it is the language, run the word through the DFA. If you reach an accepting state, it is in the language. If you get stuck (dungeon state), it's not in the language.

A language specified by the DFA is a set of words accepted by it

To take the complement of the language specified by a DFA, change all accepting states to non-accepting, and non-accepting states to accepting

A non-deterministic finite automaton (NFA) has multiple choices of transitions for an input symbol. We want to accept if any path leads to an accepting state.

We have two DFAs defining:

1. The set of natural numbers written in decimal without leading zeros
2. The set of natural numbers written in hexadecimal, prefixed with 0x

We want , so lets combine them:

Problem: if we have 0, how do we know which way to go?

A NFA is a 5-tuple (like a "DFA Space")

• is a finite alphabet (input symbols)
• is a finite set of states
• is the start state
• is the set of accepting states
• : is the transition function ( means a set of states from )

which is the same as the extended transition function for a DFA, except we take the union of any of the "next states".

A word is accepted by an NFA if . That is, there exists at least one "path" where the word leads to an accepting state.

from state a, optionally transition to b without consuming input