What is NFA and DFA?
NFA(Nondeterministic Finite Automata) means where the transition from a state can be multiple next states for each input symbol. NFA also has five tuples as DFA, but different transition functions, as shown below:
( Q, ∑, δ, q0, F )
where,
Q : represents the finite set of states.
∑ : represents a finite set of symbols known as alphabets.
δ : represents the transition function where δ: Q x ∑ →2Q.
q0 : is an initial state.
F : is a final state.
DFA(Deterministic Finite Automata) is a finite-state machine that accepts or rejects a given string of symbols by running through a state sequence that is uniquely determined by the string in the theory of computation.
It is represented as 5 tuples, thats are as folllows
(Q, ∑, δ, q0, F)
where,
Q : represents the finite states.
∑ : represents the is a finite set of symbols, also called the alphabet.
δ : represents the transition function where δ: Q × ∑ → Q.
q0 : represents the initial state from where any input is processed.
F : represents the set of the final state of Q.
Turing Machine
The Turing machine, first proposed by Alan Turing in 1936, is a powerful model for computation. Similar to a finite automaton but with unlimited, unrestricted memory, the Turing machine accurately models a general purpose computer.
It uses an infinite tape as memory and a tape head that can read, write, and move along the tape. The Turing machine can theoretically perform any computation a real computer can, making it a robust model of computation.
However, some problems are unsolvable even for a Turing machine, surpassing the theoretical limits of computation.
The tape initially contains only the input string and is blank everywhere else. The machine can write any information it needs to store on the tape. To read the written information, the machine moves its head back over it.
The machine continues computing until it produces an output, which is either "accept" or "reject" obtained by entering designated accepting or rejecting states. If the machine enters neither an accepting nor a rejecting state, it will continue computing forever without halting.
Schematic of a Turing machine
The Turing machine differs from finite automata in several key ways:
1. A Turing machine can both write on the tape and read from it, while finite automata can only read input.
2. The Turing machine's read-write head can move left and right along the tape, but a finite automaton's input head can only move in one direction.
3. The Turing machine uses an infinite tape, while finite automata have finite input.
4. Turing machines immediately reject or accept based on their current state, whereas finite automata only accept or reject once the entire input is processed.