[Verse 1] Two machines that speak the same tongue Different paths but songs they've sung Are identical in every way Equivalent we always say When languages match perfectly Though states may differ drastically [Chorus] Fill the table, mark the pairs Find the states that just don't care About each other's destiny Distinguishable they'll always be Minimal and unique it stands The smallest automaton in your hands [Verse 2] Draw a grid of every state Cross them out when they can't relate If one accepts and one rejects Mark that pair, show disrespect Keep on going, mark some more Till no new marks can you explore [Chorus] Fill the table, mark the pairs Find the states that just don't care About each other's destiny Distinguishable they'll always be Minimal and unique it stands The smallest automaton in your hands [Bridge] Faster execution waits Fewer transistors, fewer gates Memory shrinks when redundance dies Optimization's greatest prize Merge the unmarked, keep the rest Your minimal machine's the best [Verse 3] Algorithm guarantees Uniqueness up to naming sprees Call them A or call them One The structure's carved, the work is done No smaller DFA exists Mathematics never twists [Chorus] Fill the table, mark the pairs Find the states that just don't care About each other's destiny Distinguishable they'll always be Minimal and unique it stands The smallest automaton in your hands [Outro] Equivalent machines unite In minimal form, burning bright Table-filling shows the way To the leanest DFA
← 6 Non-Regular Languages & the Pumping Lemma | 1 Context-Free Grammars (CFG) →