Finite Automata(DFA)
Chomsky-Hierarchy
An automata is an abstract computing device (or machine),every automata consist of some essential features as in real computer.it has a mechanism for reading input.The input is assumed to be a sequence of symbol over a given alphabet and is placed on an input tape (or written on an input file)
The automata can produce output of some form.If the output in response to an input string is binary(say , accept of reject),then it is called an accepter.If it produces an output sequence in response to an input sequence, then it is called a transducer(or automata with output).
The automata may have a temporary storage, consisting of an unlimited number of cells,each capable of holding a symbol from an alphabet(which may be different from the input alphabet) .The automata can both read and change the contents of the storage cells in the temporary storage.
A deterministic automata is one in which each move (transition from one state to another) is unequally determined by current configuration.
Finite state Machine:-
Simplest model of computation
Very limited memory
Imp:-If the internal state, input and contents of storage are known,it is possible to predict the future behavior of the automata.this is said to be deterministic otherwise it is non-deterministic
An automata is an abstract computing device (or machine),every automata consist of some essential features as in real computer.it has a mechanism for reading input.The input is assumed to be a sequence of symbol over a given alphabet and is placed on an input tape (or written on an input file)
The automata can produce output of some form.If the output in response to an input string is binary(say , accept of reject),then it is called an accepter.If it produces an output sequence in response to an input sequence, then it is called a transducer(or automata with output).
The automata may have a temporary storage, consisting of an unlimited number of cells,each capable of holding a symbol from an alphabet(which may be different from the input alphabet) .The automata can both read and change the contents of the storage cells in the temporary storage.
A deterministic automata is one in which each move (transition from one state to another) is unequally determined by current configuration.
Finite state Machine:-
Simplest model of computation
Very limited memory
Imp:-If the internal state, input and contents of storage are known,it is possible to predict the future behavior of the automata.this is said to be deterministic otherwise it is non-deterministic
No comments