AlgoVerse

کمینه‌سازی DFA

حالت‌های هم‌ارز یک ماشین قطعی را یکی می‌کند: از تقسیم به پذیرش و غیرپذیرش شروع می‌کند و دسته‌ها را تا جایی می‌شکند که دیگر شکستنی نباشند.

دو حالت هم‌ارزند اگر برای هر رشته‌ی ورودی، هر دو به پذیرش برسند یا هیچ‌کدام. حالت‌های هم‌ارز را می‌شود یکی کرد؛ نتیجه ماشین کمینه است که برای هر زبان منظم (به‌جز نام‌گذاری حالت‌ها) یکتاست.

ادامه‌ی توضیح ↓
ورودی:
delta 5×3خروجی PDF

ماشینی ۵ حالته برای «با ab تمام می‌شود»؛ حالت ۳ با ۰ و حالت ۴ با ۱ هم‌ارز است و DFA کمینه ۳ حالت دارد. هر سطر: [بعد از a، بعد از b، پذیرش].

  1. def minimize(delta):
  2. # delta: one row per state: [state after a, state after b, accepting (1) or not (0)].
  3. n = len(delta)
  4. if any(t >= n for row in delta for t in row[:2]):
  5. return None
  6. block = [1 if row[2] else 0 for row in delta]
  7. table = [[q, delta[q][0], delta[q][1], block[q]] for q in range(n)]
  8. while True:
  9. # Two states stay together only if their blocks agree and so do the blocks they go to.
  10. signature = [(block[q], block[delta[q][0]], block[delta[q][1]]) for q in range(n)]
  11. kinds = sorted(set(signature))
  12. new = [kinds.index(sig) for sig in signature]
  13. for q in range(n):
  14. table[q][3] = new[q]
  15. if len(kinds) == len(set(block)):
  16. break
  17. block = new
  18. return len(set(block))

ناوردا: دو حالت در دسته‌های جدا هیچ‌وقت هم‌ارز نیستند: رشته‌ای هست که یکی را به پذیرش می‌برد و دیگری را نه.

شروع اجرا

block—

جدول هنوز خالی است.

متغیرهای محلی

نارنجی = در همین گام عوض شد

delta list

[1, 3, 0][1, 2, 0][1, 3, 1][4, 3, 0][4, 2, 0]

Call stack

  1. minimize()خط 1
گام ۱ از ۴۰
خط سیاه = refined, stable · خط نارنجی = گام کلیدیsplit_accepting: 0/1 · refined: 0/1 · stable: 0/1
    توضیح

    ایده

    دو حالت هم‌ارزند اگر برای هر رشته‌ی ورودی، هر دو به پذیرش برسند یا هیچ‌کدام. حالت‌های هم‌ارز را می‌شود یکی کرد؛ نتیجه ماشین کمینه است که برای هر زبان منظم (به‌جز نام‌گذاری حالت‌ها) یکتاست.

    ریز کردن افراز (روش مور)

    1. حالت‌ها را به دو دسته تقسیم کن: پذیرش و غیرپذیرش (رشته‌ی تهی آن‌ها را جدا می‌کند).
    2. هر دسته را بشکن: دو حالت با هم می‌مانند فقط اگر با a به یک دسته بروند و با b هم به یک دسته.
    3. تا وقتی دسته‌ای شکست، تکرار کن. وقتی هیچ دسته‌ای نشکست، هر دسته یک حالت ماشین کمینه است.

    هزینه

    حداکثر n دور، هر دور O(n): O(n²). روش هاپکرافت با انتخاب زیرکانه‌ی دسته‌ها به O(n log n) می‌رسد.

    ورودی

    هر سطر یک حالت است: [بعد از a، بعد از b، پذیرش (۱) یا نه (۰)]؛ حالت شروع ۰ است.