Discrete Mathematics/Finite state automata

Deterministic finite automaton Formally, a Deterministc Finite Automaton (DFA) is a 5-tuple where: Q is the set of all states. is the alphabet being considered. is the set of transitions, including exactly one transition per element of the alphabet per state. is the single starting state. F is the set of all accepting states. For a DFA, can be viewed as a function from . Example: Consider the DFA with transitions given by table: a b p q p q p q It is easy to verify that this DFA accepts the input "aaa". Nondeterministic finite automaton Similarly, the formal definition of a Nondeterministic Finite Automaton is a 5-tuple where: Q is the set of all states. is the alphabet being considered. is the set of transitions, with transitions and any number of transitions for any particular input on every state. is the single starting state. F is the set of all accepting states. For a NFA, can be viewed as a function from where is the power set of . Note that for both a NFA and a DFA, is not a set of states. Rather, it is a single state, as neither can begin at more than one state. However, a NFA can achieve similar function by adding a new starting state and epsilon-transitioning to all desired starting states. The difference between a DFA and an NFA being the delta-transitions are allowed to contain epsilon-jumps(transitions on no input), unions of transitions on the same input, and no transition for any elements in the alphabet. For any NFA , there exists a DFA such that Finite-state automaton