Project 13 - Hopcroft’s Algorithm for DFA Minimization

By: Yu Cao, Brian Tran, Yog Tadhani

Go back to home page

Executive Summary

• Executive Summary

Implementation

• Implementations:
  • C++
  • Java
  • Python
  • io
    • test input 1
    • test output 1
    • test input 2
    • test output 2
    • test input 3
    • test output 3

Input Schema: - Line 1: N S A (num states, alphabet size, num accepting states) - Line 2: c1 c2 … cN (state symbols, space-separated) - Line 3: p1 p2 … pS (alphabet symbols, space-seperated) - Line 4: start_state - Line 5: a1 a2 … aA (accepting states, space-separated) - Line 6: src symbol dest (one transition per line, N*S lines total)

Slides

• Presentation Slides

Programming Challenge

• Programming Challenge
  • Solutions:
    • Python
  • Test Cases:
    • Case 1 input
    • Case 1 output
    • Case 2 input
    • Case 2 output
    • Case 3 input
    • Case 3 output
    • Case 4 input
    • Case 4 output
    • Case 5 input
    • Case 5 output
    • Case 6 input
    • Case 6 output
    • Case 7 input
    • Case 7 output
    • Case 8 input
    • Case 8 output
    • Case 9 input
    • Case 9 output
    • Case 10 input
    • Case 10 output
    • Case 11 input
    • Case 11 output
    • Case 12 input
    • Case 12 output
    • Case 13 input
    • Case 13 output
    • Case 14 input
    • Case 14 output
    • Case 15 input
    • Case 15 output
    • Case 16 input
    • Case 16 output
    • Case 17 input
    • Case 17 output
    • Case 18 input
    • Case 18 output
    • Case 19 input
    • Case 19 output
    • Case 20 input
    • Case 20 output