Finite Automation (FA)
Finite Automation
i) Finite Acceptor (FA without output)
- Deterministic: DFA
- Non-deterministic: NFA
ii) Finite Transducer(FA with output)
- Moore Machine
- Mealy Machine
Finite automata is a categorized into two types:-
1) Finite automata with output : This is of two types Mealy Machines and moore Machine.
a) In Mealy Machine the output is associated with transition (state and input symbol)
b) In Moore Machine output is associated with the state
2) Finite automata without output : This is of two types DFA and NFA
a) DFA : It is deterministic finite automata,for every input symbol in DFA there is an exactly one transition from each state of finite automata.It accepts all string that are present in the language by halting in a final stage and rejects all strings that are not present in the language by halting in a non-final state.
b) NFA : It is a non deterministic finite automata for every input symbol in NFA there is at least one transition or no transitions from each state of finite automata.It accepts all strings that are present in the language either by halting in a final state or by halting in a dead configuration.
Model of Finite Automata:-
Input tape contains a string over the given input alphabet, and read head is a pointer which reads one input symbol at a time and moves to the next symbol.Finite control contains set of state and a transitions function to take an action based on current state and input symbol scanned.
Deterministic Finite Automata (DFA)
For evey input symbol of alphabet there is an exactly one transition from every state of finite automata is called as DFA.
DFA covers tansitions for all valid and invalid strings in the given regular language. For every valid string , DFA reaches to one of its final state and for every invalid string it reaches to non-final state.
i) Finite Acceptor (FA without output)
- Deterministic: DFA
- Non-deterministic: NFA
ii) Finite Transducer(FA with output)
- Moore Machine
- Mealy Machine
Finite automata is a categorized into two types:-
1) Finite automata with output : This is of two types Mealy Machines and moore Machine.
a) In Mealy Machine the output is associated with transition (state and input symbol)
b) In Moore Machine output is associated with the state
2) Finite automata without output : This is of two types DFA and NFA
a) DFA : It is deterministic finite automata,for every input symbol in DFA there is an exactly one transition from each state of finite automata.It accepts all string that are present in the language by halting in a final stage and rejects all strings that are not present in the language by halting in a non-final state.
b) NFA : It is a non deterministic finite automata for every input symbol in NFA there is at least one transition or no transitions from each state of finite automata.It accepts all strings that are present in the language either by halting in a final state or by halting in a dead configuration.
Model of Finite Automata:-
Input tape contains a string over the given input alphabet, and read head is a pointer which reads one input symbol at a time and moves to the next symbol.Finite control contains set of state and a transitions function to take an action based on current state and input symbol scanned.
Deterministic Finite Automata (DFA)
For evey input symbol of alphabet there is an exactly one transition from every state of finite automata is called as DFA.
DFA covers tansitions for all valid and invalid strings in the given regular language. For every valid string , DFA reaches to one of its final state and for every invalid string it reaches to non-final state.
No comments