In this section you will learn the definition of the automaton and know different types of automaton.
Definition of automaton
Automaton is the model calculation which is the subject of research of languages and automata theory. The purpose of using automaton is to solve in a finite number of steps,if any word should or should not be considered the language of the automaton. Automata theory is the result of research initiated by A. Turing.
Automaton over the alphabet A is a system A=(S,f),where S –is any finite set called the set of states,and f:S x A → S –is a transition function.
A finite-state automaton is a mathematical abstraction sometimes used to design digital logic or computer programs. It is a behavior model composed of a finite number of states,transitions between those states,and actions,similar to a flow graph in which one can inspect the way logic runs when certain conditions are met.
Example
The picture shows a very simple finite automaton that behaves in a stable manner when the input is set to A,and changes its state when it encounters B. He starts work on the state S1,and after reading each symbol goes to the state Sj (where j = 1 or 2)
- start state –S1
- S1 →1 S1
- S1 →0 S2
- S2 →1 S2
- S2 →0 S1
What is the main feature of a finite-state automaton?- What is the difference between DFA and NFA?
Automaton may be represented by state diagram or state transition table.
Finite automata can be divided into deterministic and non-deterministic.
Deterministic finite automaton
Deterministic finite automaton (DFA) is a finite state machine accepting finite strings of symbols. For each state,there is a transition arrow leading out to a next state for each symbol. Upon reading a symbol,a DFA jumps deterministically from a state to another by following the transition arrow. Deterministic means that there is only one outcome or move back to the same state.
Deterministic finite automaton AD is a 5-tuple AD = <N,V,M,S,Z>,where:
N –a finite set of states
V- a finite set of input symbols called the alphabet
M –a transition function M:(N x V) &rorr;N
S –a start state
Z –a set od accept states
A DFA has a start state where computations begin,and a set of accpet states which help define when a computation is successful.
Nondeterministic finite automaton
Nondeterministic finite automaton (NFA) is a finite state machine where for each pair of state and input symbol there may be several possible next states.
Nondeterministic finite automaton AN is a 5-tuple AN = <N,V,M,S,Z>,where:
N –a finite set od states
V- a finite set of input symbols
M –a transition function M:(N x V) ->2^N
S –an initial state
Z –a set od states distinguished as accepting states
Nondeterministic automaton,in contrast to DFA,after reading the symbol can go to one of several different states.
Interesting…
For every NFA adeterministic finite state machine (DFA) can be found that accepts the same language. Therefore it is possible to convert an existing NFA into a DFA for the purpose of implementing a (perhaps) simpler machine. This can be performed using the powerset construction,which may lead to an exponential rise in the number of necessary states.
Questions
If you do not know the answer to these questions,read again the above content.
