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 dfa1.jpg where

A dfa operates as follows:

currentState := dfa6.jpg
while more input exists
currentInput := next_input_symbol
advance input to right
currentState := dfa7.jpg (currentState,currentInput)
if currentState dfa8.jpg then ACCEPT else REJECT

Transition Graphs

To visualize a dfa, we use a transition graph


See Example 2.1 in Linz textbook.

Definition
The extended transition function dfa13.jpg is defined recursively:

dfa14.jpg

dfa15.jpg

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

Languages

Definition
The language accepted by a dfa dfa16.jpg
is dfa17.jpg

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

Note that above dfa18.jpg and dfa19.jpg 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 dfa20.jpg may also be convenient.

Regular Language

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

Dfas define the family of languages called regular.

See examples in the Linz textbook.


[Next]


Copyright © 2000, H. Conrad Cunningham
Last modified: Wed Aug 16 19:46:31 2000