Equivalence of Finite Automata

The Problem A Simple Algorithm Hopcroft Karp Algorithm Correctness Conclusion A linear algorithm for testing Equivalence of Finite Automata (Hopcroft and Karp, 1971) Presented by Chintan Rao Vijeth D November 24, 2009 Automata Theory & Computability, Seminar An Algorithm for testing equivalence of nite automata institution-logo The Problem A Simple Algorithm Hopcroft Karp Algorithm Correctness Conclusion Outline 1 The Problem 2 A Simple Algorithm Algorithm Example Analysis Scope for Improvement 3 Hopcroft Karp Algorithm De nitions The Idea Algorithm Examples

4 Correctness 5 Conclusion Automata Theory & Computability, Seminar An Algorithm for testing equivalence of nite automata institution-logo The Problem A Simple Algorithm Hopcroft Karp Algorithm Correctness Conclusion The Problem Given two DFAs on same alphabet, we intend to determine if they accept the same language. M1 = (Q1; ; 1;s1;F1) M2 = (Q2; ; 2;s2;F2) Is L(M1) = L(M2) ? Automata Theory & Computability, Seminar An Algorithm for testing equivalence of nite automata institution-logo The Problem A Simple Algorithm Hopcroft Karp Algorithm Correctness Conclusion Algorithm Example Analysis Scope for Improvement A Simple Algorithm 1 Minimize M1 and M2 to get canonical DFAs, M01 and M02. Time complexity = O(j jn log n) 2 Check if M01 and M02 are equivalent. Time complexity = O(j jm) where m is the number of states in M01 (or M02). Overall complexity = O(j jn log n) Automata Theory & Computability, Seminar An Algorithm for testing equivalence of nite automata institution-logo The Problem A Simple Algorithm Hopcroft Karp Algorithm Correctness Conclusion Algorithm Example Analysis Scope for Improvement Example Automata Theory & Computability, Seminar An Algorithm for testing equivalence of nite automata institution-logo The Problem A Simple Algorithm Hopcroft Karp Algorithm Correctness Conclusion Algorithm Example Analysis Scope for Improvement Example Automata Theory & Computability, Seminar An Algorithm for testing equivalence of nite automata institution-logo The Problem A Simple Algorithm Hopcroft Karp Algorithm Correctness Conclusion Algorithm Example Analysis Scope for Improvement Equivalence Classes Automata Theory & Computability, Seminar An Algorithm for testing equivalence of nite automata institution-logo The Problem A Simple Algorithm Hopcroft Karp Algorithm Correctness Conclusion Algorithm Example Analysis Scope for Improvement Equivalence Classes Automata Theory & Computability, Seminar An Algorithm for testing equivalence of nite automata institution-logo The Problem A Simple Algorithm Hopcroft Karp Algorithm Correctness Conclusion Algorithm Example Analysis Scope for Improvement Equivalence Classes Automata Theory & Computability, Seminar An Algorithm for testing equivalence of nite automata institution-logo The Problem A Simple Algorithm Hopcroft Karp Algorithm Correctness Conclusion Algorithm Example Analysis Scope for Improvement Scope for improvement Automata Theory & Computability, Seminar An Algorithm for testing equivalence of nite automata institution-logo The Problem A Simple Algorithm Hopcroft Karp Algorithm Correctness Conclusion Algorithm Example Analysis Scope for Improvement Scope for improvement Automata Theory & Computability, Seminar An Algorithm for testing equivalence of nite automata institution-logo The Problem A Simple Algorithm Hopcroft Karp Algorithm Correctness Conclusion Algorithm Example Analysis Scope for Improvement Scope for...

Website: drona.csa.iisc.ernet.in | Filesize: -
No of Page(s): 50
Download Equivalence of Finite Automata.pdf