Theory of Computation | NFA - Non-deterministic Finite Automata
Prerequisites : Symbols, Alphabets, Strings and Language Types of Automata and Representation. DFA - Deterministic Finite Automata When there is a chance for multiple state changes on a given single input, the non-deterministic in autoama handles the scenario. The non determinism may even lead a in to null states. Non-deterministic Finite Automata(NFA) are pseudo machines, means cannot be implemented in reality, even though they are finite state machines. But of course NFA are very useful to resolve problem by exhaustive searching and backtracking. A null state is represented using Greek letter Φ The figure represents a NFA, which accepts all strings which starts with alphabet 'a' Here we have two states, A and B. so, set of all states Q = {A, B} and set of all symbols Σ = {a, b} Final state F = {B} and initial state q 0 = { A } When input 'a' is given to state A , the state changes to B But...