DHARMINTRODUCTION TO LANGUAGES AND FINITE AUTOMATA 181where LM contains those set of strings that are accepted by automaton M, and remaining
string (Σ – LM) are those that are discarded or rejected by M. Hence, LM and Σ- LM are two
disjoint sets which never meet with reference to a particular automaton M, i.e.,
LM ∩ (Σ* – LM) = Φ
Note. Set LM contains infinitely many strings or a language of a DFA contains infinite number of
strings but an automaton has a finite amount of space that is only available space to allocate to finite or
infinitely long strings. Hence, there is a mechanism used to describe a infinitely long string into a finite
number of symbols (detail discussion is out of scope of the topic) but for brief discussion see the topic
languages under section basic concepts of automata in the beginning of this chapter.
7.3 NON DETERMINISTIC FINITE STATE AUTOMATA (NDFSA)/
NON DETERMINISTIC FINITE STATE MACHINE (NDFSM)/
NON DETERMINISTIC FINITE AUTOMATA (NDFA)/NFA
In the previous section we have discussed deterministic finite state automata (DFA) whose
state transitions are deterministic which means that there is one and only one exit arc from
each state on an input symbol. So we can say that DFA gives somewhat static view of the finite
automata. Now we will discuss a dynamic/flexible view of the finite automata whose state
transitions are not of deterministic nature (non-deterministic), which means that there is the
possibility of multiple transitions on some input symbols from a single state. So, the automata
of such category are known as nondeterministic finite state automata (NDFSA/NDFSM/NDFA/
NFA). The feature of dynamism introduced in the finite automata provides more power to the
finite automata. The abstract view of the NFA shown in Fig. 7.16 is similar to the DFA.
a bb... a aTH
NDA
Mq 0bFig. 7.167.3.1 Definition
We can define a nondeterministic finite automaton (NFA) with following tuples,
l Q, a finite set of states,
l Σ, a finite set of input symbols,
l q 0 , an initial state, where q 0 ∈ Q
l F, a set of final state/s, where F is the subset of state Q i.e., (F ⊆ Q),
l δ, a transition function which defines the next state reachable from current state
over an input symbol. It reaches to either no state or single state or two/more states.
l No state transition means, there is no actual transition define from a state on
that symbol or there is no exit arc from that state on that symbol.
l Single state transition means, there is a single transition define from a state on
that symbol or there is a single exit arc from that state.