explain the similaritie between derministic and non-derministic automata

A deterministic finite automaton is an automaton where for each state there exits exactly one following state for each possible input. A non-deterministic finite automaton may have multiple (or no) following states for a given state and input.

Dear Sudharama,

In the automata theory, a nondeterministic finite automaton (NFA) or nondeterministic finite state machine is a finite state machine where from each state and a given input symbol the automaton may jump into several possible next states. This distinguishes it from the deterministic finite automaton (DFA), where the next possible state is uniquely determined. Although the DFA and NFA have distinct definitions, a NFA can be translated to equivalent DFA using powerset construction, i.e., the constructed DFA and the NFA recognize the same formal language. Both types of automata recognize only regular languages. NFAs were introduced in 1959 by Michael O. Rabin and Dana Scott, who also showed their equivalence to DFAs.

NFAs are sometimes studied by the name subshifts of finite type. NFAs have been generalized multiple ways, e.g., nondeterministic finite automaton with ε-moves, pushdown automaton, ω-automaton,probabilistic automata.

Cracking IIT just got more exciting,It s not just all about getting assistance from IITians, alongside Target Achievement and Rewards play an important role. ASKIITIANS has it all for you, wherein you get assistance only from IITians for your preparation and win by answering queries in the discussion forums. Reward points 5 + 15 for all those who upload their pic and download the ASKIITIANS Toolbar, just a simple  to download the toolbar….

So start the brain storming…. become a leader with Elite Expert League ASKIITIANS

Thanks

Aman Bansal

Askiitian Expert

Dear Sudharma,

 A nondeterministic finite automata is a quintuple <Q,å,d,q0,F>; where:             

• Q is a finite set of states;
• å is a finite set of input symbols;
• d is the, possibly partial, transition function
• d:A transition function that takes a state in Q and an input symbol in I as arguments and returns a subset of Q.
•  q0 element of Q is called the initial state;
• F contained in Q is called the set of final states.

                                The above definition states that a nondeterministic finite automaton  can exhibit several different transition sequences for a given state and a given input.

                            An input string is accepted by a nondeterministic finite automaton if and only if at least one of the possible transition sequences, defined by the input, leads to a final state.

Cracking IIT just got more exciting,It s not just all about getting assistance from IITians, alongside Target Achievement and Rewards play an important role. ASKIITIANS has it all for you, wherein you get assistance only from IITians for your preparation and win by answering queries in the discussion forums. Reward points 5 + 15 for all those who upload their pic and download the ASKIITIANS Toolbar, just a simple  to download the toolbar….

So start the brain storming…. become a leader with Elite Expert League ASKIITIANS

Thanks

Aman Bansal

Askiitian Expert