Equivalence of DFAs and NFAs.pptx

Theory of Computation

1. Equivalence of DFAs and NFAs Submitted by – Samyak Jain (MCA/25014/2022) Submitted to – Madan Mohan Sir

2. DFA (Deterministic Finite Automata) It is the simplest model of computation. It has a very limited memory. DFA can be defined using five tuple (Q , ∑ , q0 ,F , δ ) Q = set of all states ∑ = inputs q0 = start state/initial state F = set of final states δ = transition function Q × ∑ -> Q

3. NFA ( NonDeterministic Finite Automata ) In NFA , given the current state there could be multiple next state. Next state may be chosen at random. NFA can be defined using five tuple (Q , ∑ , q0 ,F , δ ) Q = set of all states ∑ = inputs q0 = start state/initial state F = set of final states δ = transition function Q × ∑ -> 2^Q

4. Equivalence of DFA and NFA Two Automata are said to be equivalent if they accept the same language. Every DFA is an NFA , but not vice versa. But there is an equivalent DFA for every NFA.

5. NFA to DFA conversion (Using subset conversion method) Ex -> L = { set of all string over (0,1) that starts with ‘0’}

6. Ex - > L = { set of all string over {0,1} that ends with ‘01’ }

7. Reference :- https://youtu.be/--CSVsFIDng https://neuraldump.net/2017/11/nfa-and-dfa-equivalence-theorem-proof-and-example/

8. THANK YOU!!!