Sunday, 3 November 2013

Finite Automata

finite automaton (FA, also called a finite-state automaton or a finite-state machine) is a mathematical tool used to describe processes involving inputs and outputs. An FA can be in one of several states and can switch between states depending on symbols that it inputs. Once it settles in a state, it reads the next input symbol, performs some computational task associated with the new input, outputs a symbol, and switches to a new state depending on the input. Notice that the new state may be identical to the current state.

Figure 1 shows an example of a two-state FA that can be used to add binary numbers. The FA starts in state 1 (no carry) and inputs a pair of bits. If the pair is 11, the FA outputs a 0 and switches to state 2 (carry), where the next pair of bits is input and is added to a carry bit of 1. Table F.1 shows the individual steps in adding the two 6-bit numbers 14and 23 (these are actually 5-bit numbers, but the simple design of this FA requires that an extra 0 bit be appended to the left end of every number). Since adding numbers is done from right to left, the six columns of the table should also be read in this direction.

Definition: A DFA is 5-tuple or quintuple M = (Q, ∑, δ, q0, A) where
Q is non-empty, finite set of states.
∑ is non-empty, finite set of input alphabets.
δ is transition function, which is a mapping from Q ∑ to Q.
q0 ∈ Q is the start state.
A  Q is set of accepting or final states.
Note: For each input symbol a, from a given state there is exactly one transition (there can be no transitions from a state also) and we are sure (or can determine) to which state the machine enters. So, the machine is called Deterministic machine. Since it has finite number of states the machine is called Deterministic finite machine or Deterministic Finite Automaton or Finite State Machine (FSM).
The language accepted by DFA is
L(M) = { w | w  ∑* and δ*(q0, w) ∈ A }
The non-acceptance of the string w by an FA or DFA can be defined in formal notation as:
= { w | w  ∑* and δ*(q0, w)  A }

So, the DFA which accepts strings of a’s and b’s starting with the string ab is given by M
= (Q, ∑ , δ, q0, A) where

Q = {q0, q1, q2, q3}
∑ = {a, b}
q0­ is the start state
A = {q2}.
δ is shown by the transition table 3.