Chap ter 1
DFA and NFA
1.1 DETERMINISTIC FINITE AUTOMATA (DFA)
1.1.1 Autom ata—What is it?
An automaton is an abstract model of a digital computer. An automaton has a
mechanism to read input, which is a string over a given alphabet. This input is
actually written on an “input file”, which can be read by the automaton but
cannot change it.
Input file is divided into cells, each of which can hold one symbol. The
automaton has a temporary “storage” device, which has unlimited number of
cells, the contents of which can be altered by the automaton. Automaton has a
control unit, which is said to be in one of a finite number of “internal states”.
The automaton can change state in a defined way.
1.1.2 Types of Autom a ton
(a) Deterministic Automata
(b) Non-deterministic Automata
A deterministic automata is one in which each move (transition from one
state to another) is unequally determined by the current configuration.
If the internal state, input and contents of the storage are known, it is
possible to predict the future behaviour of the automaton. This is said to be
deterministic automata otherwise it is nondeterminist automata.
Control Unit
Output
Input File
Storage
Fig. Autom a ton