10-04-2017, 08:48 PM
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...cs.fit.edu%2F dmitra%2FFormaLang%2FFiniteAutomata.ppt&ei=6xK0TLi7O5GuvgPH7p2lCg&usg=AFQjCNHisYhUpHEqskwFAiFvpNWATIz58Q