Deterministic Finite State Automata

One-way, infinite tape, broken into cells
One-way, read-only tape head.
Finite control, I.e., a program, containing the position of the read head, current symbol being scanned, and the current “state.”
A string is placed on the tape, read head is positioned at the left end, and the DFA will read the string one symbol at a time until all symbols have been read. The DFA will then either accept or reject.

Finite

Control
0
0
1
1
0



2
The finite control can be described by a transition diagram:

Example #1:


1 0 0 1 1

q0 q0 q1 q0 q0 q0
One state is final/accepting, all others are rejecting.
The above DFA accepts those strings that contain an even number of 0’s

q0
q1
0

0

1

1



3
Example #2:

a c c c b accepted

q0 q0 q1 q2 q2 q2
a a c rejected

q0 q0 q0 q1

Accepts those strings that contain at least two c’s

q1
q0
q2



For more information about this article,please follow the link:
http://googleurl?sa=t&source=web&cd=1&ve...tomata.ppt&ei=6xK0TLi7O5GuvgPH7p2lCg&usg=AFQjCNHisYhUpHEqskwFAiFvpNWATIz58Q