Mumbai University > Informatica Technology > Sem 4 > Automata Theory

Marks: 8

Year:May 16

• A finite automaton has a set of states, starts in a start state, and reads an input string character-by-character, each character making it switch states depending on which character it read and which state it was previously in (state-character pair); this is called the transition function or transition relation.

• Some states may also have ε-transitions, which are states the machine can go to without reading any character.

• A certain set of states are designated accept states; whether the finite automaton accepts or rejects depends on whether it's in an accept state or reject state after reading the entire string.

In a nondeterministic finite automaton, the transition relation specifies any number, including 0, 1, 2, or more, possible states that the NFA can transition to for each state-character pair.

• How it decides which one to take is neither defined nor relevant to the abstract concept, but you can pretend that it chooses uniformly at random.

This can produce many different computation paths for the same input string; and we say that an NFA accepts a string if at least one of those paths ends in an accept state.

In some sense, we can just say a deterministic finite automaton is one that isn't nondeterministic - where the transition function specifies only one future state for each state-character pair, and thus there is only one computation path on any given input string. If it ends in a designated accept state, the machine accepts.

So the key difference is whether the computation path is determined by the input string, or if there's some additional nondeterminism involved.

• But there's another difference, and it has to do with size. Obviously, any DFA can be made into an "NFA with no nondeterminism", so any language accepted by a DFA can be accepted by an NFA.

• Given an NFA, at any point in the string we can look at all the computation paths up to this point, and the set of states that at least one computation path is in; and these sets of states can be considered the states of a DFA, since this transition is deterministic.

• (If it's not obvious from this explanation, think about it a bit.) So the languages recognized by DFAs and those recognized by NFAs are identical.

• However, if you take an NFA with n states and make a DFA out of it using this method, that DFA will have 2^n states, and there are some languages where you can't actually get more efficient than that.

• It's also proven that the languages that can be described by regular expressions are the same set as those that can be recognized by DFAs or NFAs, but given a regular expression of length n, the smallest NFA has O(n) states, while the smallest DFA in general has O(2^n) states.