CSci 311: Models of Computation
Fall Semester 2000
Lecture Notes

Deterministic Finite Acceptors

Acceptors

Reference: This material is based on section 2.1 of the Linz textbook.

Definition

A deterministic finite acceptor or dfa is defined by the tuple where

• Q is a finite set of internal states.

• is a finite set of symbols called the input alphabet.

• is a total function called the transition function.

• is the initial state.

• is a set of final states.

A dfa operates as follows:

currentState :=

while more input exists

currentInput := next_input_symbol

advance input to right

currentState := (currentState,currentInput)

if currentState then ACCEPT else REJECT

Transition Graphs

To visualize a dfa, we use a transition graph

• Vertices represent states
  -- labels are state names
  -- exactly one vertex

• Directed edges represent transitions
  -- label on edge is current input symbol
  -- directed edge with label if and only if

See Example 2.1 in Linz textbook.

Definition

The extended transition function is defined recursively:

The extended transition function gives the state of the automaton after reading a string.

Languages

Definition

The language accepted by a dfa
is

That is, L(M) is the set of all strings on the input alphabet accepted by automaton M.

Note that above and are total functions (defined for all strings).

See example 2.2 in the Linz textbook.

A trap state is a state from which the automaton can never "escape".

Transition graphs are quite convenient for understanding finite automata.

For other purposes--such as representing finite automata in programs-- a tabular representation of transition function may also be convenient.

Regular Language

Definition

A language L is called regular if and only if there exists a dfa M such that .

Dfas define the family of languages called regular.

See examples in the Linz textbook.

[Next]