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 statesa special start statea set of final (or accepting) statesa set of transitions T from one state to another, labeled with chars in CAs noted above, 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 stateIf the next input char matches the label on a transition from the current state to a new state, go to that new stateContinue making transitions on each input charIf no move is possible, then stopIf in accepting state, then accept
- Subject:
- Computer Science
- Material Type:
- Module
- Author:
- Deepika Dash
- Date Added:
- 07/21/2016
