Ask a Teacher

Search



What do you mean by Finite Automata?

A finite automaton (FA) is a simple idealized machine used to recognize patterns within input taken from some character set (or alphabet) C. The job of an FA is to accept or reject an input depending on whether the pattern defined by the FA occurs in the input.

A finite automaton consists of:

         a finite set S of N states
         a special start state
         a set of final (or accepting) states
         a set of transitions T from one state to another, labeled with chars in C

we can represent a FA graphically, with nodes for states, and arcs for transitions.

We execute our FA on an input sequence as follows:

     Begin in the start state

     If the next input char matches the label on a transition from the current state to a new state, go to that new state

     Continue making transitions on each input char

     If no move is possible, then stop

     If in accepting state, then accept


comments powered by Disqus