مینیم‌سازی دی‌اف‌ای
وضعیت‌های غیر قابل تشخیص > الگوریتم هوپکرافت

یک الگوریتم برای ادغام کردن وضعیت‌های غیرقابل تشخیص از یک دی‌اف‌ای، بر طبق (هوپکرافت ۱۹۷۱)، بر اساس تصفیهٔ بخشی است، بخش‌کردن وضعیت‌های دی‌اف‌ای به گروه‌ها بوسیلهٔ رفتارشان. این گروه‌ها کلاس‌های هم‌ارزی از رابطه هم‌ارزی مای‌هیل-نرود را بیان می‌کنند، که به موجب آن هر دو وضعیت از یک بخش هم‌ارزند اگر برای هر رشتهٔ ورودی رفتار مشابه داشته باشند. یعنی، برای هر دو وضعیت p1 و p2 که به یک کلاس هم‌ارزی در بخش P متعلق باشند، حالتی خواهد بود که برای هر ورودی کلمهٔ w، اگر فردگذارهای تعیین شده با w از دو وضعیت p1 و p2 را دنبال کند یا به قبول وضعیت‌ها در دو حالت می‌رسد یا به رد دو وضعیت در هر دو حالت می‌رسد؛ ممکن نیست برای w که p1 را یک وضعیت پذیرش بگیرد و p2 رایک وضعیت رد بگیرد یا برعکس.
شبه‌کد زیر الگوریتم را توضیح می‌دهد:
P := {F, Q \ F};
W := {F};
while (W is not empty) do
     choose and remove a set A from W
     for each c in ∑ do
          let X be the set of states for which a transition on c leads to a state in A
          for each set Y in P for which X ∩ Y is nonempty and Y \ X is nonempty do
               replace Y in P by the two sets X ∩ Y and Y \ X
               if Y is in W
                    replace Y in W by the same two sets
               else
                    if |X ∩ Y| <= |Y \ X|
                         add X ∩ Y to W
                    else
                         add Y \ X to W
          end;
     end;
end;
الگوریتم بایک بخش که خیلی زمخت است شروع می‌شود: هر جفت وضعیت که معادل باشند بر طبق رابطهٔ مای هیل- نرود به یک مجموعهٔ یکسان در بخش متعلق است، ولی جفت‌هایی که نامعادلند نیز ممکن است به یک مجموعه تعلق داشته باشند. این به تدریج بخش را به تعداد زیادتری از مجموعه‌های کوچکتر تصفیه می‌کند، در هر گام مجموعه‌های وضعیت‌ها را به جفت‌های زیر مجموعه تفکیک می‌کند که لزوماً نامعادلند. بخش اولیه تفکیک وضعیت‌ها به دو زیر مجموعه از وصعیت‌هاست که به وضوح یک رفتار مشابه یکدیگر ندارند: پذیرش وضعیت‌ها و رد وضعیت‌ها. سپس الگوریتم به‌طور تکراری مجموعهٔ  A از بخش جاری  و یک علامت ورودی  c را انتخاب می‌کند، و هر مجموعه از بخش را به دو زیر مجموعهٔ(احتمالاً خالی) تقسیم می‌کند: زیر مجموعهٔ وضعیت‌ها که به  A روی علامت ورودی  c منجر می‌شود، و زیر مجموعهٔ وضعیت‌ها که به  A منجر نمی‌شود. چون  A تاکنون به داشتن رفتارهای متفاوت نسبت به مجموعه‌های دیگر بخش مشخص می‌شود، زیر مجموعه‌هایی که به  A منجر می‌شوند نیز رفتار متفاوتی از آن‌هایی که به  A منجر نمی‌شوند دارند. وقتی که هیچ تقسیمی از این نوع نمی‌توان یافت، الگوریتم لم را خاتمه می‌دهد.
با داشتن یک کاراکتر ثابت  c و یک کلاس هم‌ارزی  Y که به کلاس‌های هم‌ارزی  B و  C تقسیم می‌شود، فقط یکی از  B یا  C لازم است تا کل بخش را تصیفیه کند.
مثال: فرض کنید یک کلاس هم‌ارزی  Y داریم که به کلاس‌های هم‌ارزی  B و  C تقسیم می‌شود. فرض کنید کلاس‌های  E ،  D  و  F نیز داریم ؛ D و  Eوضعیت‌ها یی باانتقال به  B  روی کاراکتر  c  دارند، در حالیکه  F انتقال‌هایی به  C روی کاراکتر  c دارد. به موجب لم، می‌توانیم یا  B یا  C را به عنوان تمیزدهنده انتخاب کنیم، بگذارید بگوییم  B . سپس وضعیت‌های  D و E با انتقال‌هایشان  به  B تقسیم می‌شوند. ولی  F، که به  B اشاره ندارد، به سادگی در هنگام تکرار جاری الگوریتم تقسیم نمی‌شود؛به وسیلهٔ تمیز دهنده‌های دیگر تصفیه خواهد شد.
هر  B یا C لازم است که به کلاس‌های مورد اشارهٔ مانند  D،  E و F به‌طورصحیح تقسیم شود-- زیر مجموعه‌ها مشاهده انجام نخواهند داد.
غایت هدف جملهٔ اگر(اگر  y در w باشد) وصله کردن  W ، مجموعهٔ تمیز دهنده‌هاست. در جملهٔ قبل در الگوریتم می‌بینیم که  Y فقط تقسیم شده‌است. 
اگر  Y در  W باشد، فقط کنار گذاشته شده‌است به عنوان وسیله‌ای که کلاس‌ها را در تکرارهای آینده تقسیم کند. بنابراین  Y بایستی بوسیلهٔ هردو تقسیمات جایگزین شود به علت مشاهدهٔ بالا. امااگر  Y در  W نباشد، تنها یکی از دو تقسیم، نه هر دو، لازم است که به  W اضافه شود به علت لم بالا. انتخاب کوچکترین از دو تقسیم تضمین می‌کند که اضافه‌کردن جدید به  W بیشتر از نصف اندازهٔ  Y نیست؛ این هستهٔ الگوریتم هوپکرافت است: چگونه سرعت می‌گیرد، چنانچه در پاراگراف بعد می‌آید.
بدترین حالت زمان اجرای این الگوریتم است O(nslogn)، که  n تعداد وضعیت‌ها و s اندازهٔ الفباست. این محدودیت از این حقیقت ناشی می‌شود که، برای هر یک از انتقال‌های  ns از اتوماتا، مجموعه‌هایی که از  Q گرفته شده‌است که شامل وضعیت هدف از انتقال است اندازه‌هایی  دارد که نسبت به یکدیگر با ضریب یک یا دو کاهش می یابد، بنابراین هر انتقال در  O(logn) از گام‌های تقسیم الگوریتم شرکت می‌کند. ساختمان دادهٔ تصفیهٔ بخش به هر گام تقسیم‌کننده اجازه می‌دهد که در زمانی متناسب باتعداد انتقال‌هایی که در آن شرکت می‌کند اجرا شود.این کاراترین الگوریتم شناخته شده را برای حل مسئله به جا می‌گذارد، و برای توزیع‌های خاصی از ورودی‌ها متوسط حالت پیچیدگی حتی بهتر است، O(nloglogn).
یک‌بار الگوریتم هوپکرافت بکار رفته‌است تا وضعیت ورودی دی‌اف‌ای به کلاس‌های هم‌ارزی گروه شوند، مینیمم دی‌اف‌ای می‌تواندبا تشکیل یک وضعیت برای هر کلاس هم‌ارزی ساخته شود.  اگر  S مجموعه‌ای وضعیت‌ها در   P ، و  s یک وضعیت در  S، و  c یک کاراکتر ورودی باشد، انتقال در مینیمم دی‌اف‌ای از وضعیت برای  S، روی ورودی  c ، می‌رود به سوی مجموعه‌ای شامل وضعیتی که اتومات ورودی برود از وضعیت  s روی ورودی  c . وضعیت اولیهٔ دی‌اف‌ای مینیمم آنی است که شامل وضعیت اولیهٔ ورودی دی‌راف‌ای است، و وضعیت‌های پذیرفتهٔ دی‌اف‌ای مینیمم آن‌هایی هستند که اعضایشان وضعیت‌های پذیرفتهٔ دی‌اف‌ای مینیمم هستند.