AlgoVerse

تبدیل NFA به DFA (ساخت زیرمجموعه)

ماشین ناقطعی را به ماشین قطعی معادل تبدیل می‌کند: هر حالت DFA مجموعه‌ای از حالت‌های NFA است که ماشین ناقطعی هم‌زمان می‌تواند در آن‌ها باشد.

در ماشین ناقطعی (NFA) از یک حالت با یک نماد ممکن است به چند حالت رفت، یا بدون خواندن نماد (با ε) جابه‌جا شد. ولی هر NFA یک ماشین قطعی (DFA) معادل دارد: حالت‌های DFA مجموعه‌هایی از حالت‌های NFA‌اند.

ادامه‌ی توضیح ↓
ورودی:
edges 13×3 · accept=10خروجی PDF

NFA تامسون برای (a|b)*abb با ۱۱ حالت (۰ تا ۱۰)؛ DFA معادل ۵ حالت دارد. هر سطر ورودی [از، نماد، به] است (۰ = a، ۱ = b، ۲ = ε).

  1. def subset_construction(edges, accept):
  2. # edges: rows [from, symbol, to] with symbol 0 = a, 1 = b, 2 = ε. The start state is 0.
  3. eps = {} # the ε-moves out of each state
  4. for f, s, t in edges:
  5. if s == 2:
  6. eps.setdefault(f, []).append(t)
  7. dstates = [closure(eps, [0])]
  8. rows = []
  9. i = 0
  10. while i < len(dstates):
  11. T = dstates[i]
  12. targets = []
  13. for c in (0, 1):
  14. moved = [t for f, s, t in edges if f in T and s == c]
  15. U = closure(eps, moved)
  16. if U not in dstates:
  17. dstates.append(U)
  18. targets.append(dstates.index(U))
  19. rows.append([i, set_text(T), targets[0], targets[1], "yes" if accept in T else ""])
  20. i = i + 1
  21. return len(dstates)
  24. def closure(eps, states):
  25. # Every NFA state reachable from these using ε-moves only.
  26. seen = set(states)
  27. stack = list(states)
  28. while stack:
  29. q = stack.pop()
  30. for t in eps.get(q, []):
  31. if t not in seen:
  32. seen.add(t)
  33. stack.append(t)
  34. return tuple(sorted(seen))
  37. def set_text(T):
  38. return "{" + ",".join(str(q) for q in T) + "}"

ناوردا: بعد از خواندن هر رشته، DFA در حالتی است که دقیقاً مجموعه‌ی حالت‌هایی است که NFA می‌توانست با همان رشته به آن‌ها برسد.

شروع اجرا

dstates—

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

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

accept10

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

edges list

[0, 2, 1][0, 2, 7][1, 2, 2][1, 2, 4][2, 0, 3][4, 1, 5][3, 2, 6][5, 2, 6][6, 2, 1][6, 2, 7][7, 0, 8][8, 1, 9][9, 1, 10]

Call stack

  1. subset_construction()خط 1
گام ۱ از ۶۲۳
خط سیاه = row_done · خط نارنجی = گام کلیدیstart: 0/1 · new_state: 0/4 · row_done: 0/5
    توضیح

    ایده

    در ماشین ناقطعی (NFA) از یک حالت با یک نماد ممکن است به چند حالت رفت، یا بدون خواندن نماد (با ε) جابه‌جا شد. ولی هر NFA یک ماشین قطعی (DFA) معادل دارد: حالت‌های DFA مجموعه‌هایی از حالت‌های NFA‌اند.

    ساخت زیرمجموعه

    • بستار ε یک مجموعه: همه‌ی حالت‌هایی که فقط با ε از آن‌ها رسیدنی‌اند.
    • حالت شروع DFA بستار ε حالت شروع NFA است.
    • برای هر حالت DFA مثل T و هر نماد c: همه‌ی حالت‌هایی که از T با c رسیدنی‌اند، و بستار ε آن‌ها، یک حالت (شاید تازه) DFA است.
    • حالتی پذیرش است که حالت پذیرش NFA را داشته باشد.

    هزینه

    در بدترین حالت 2ⁿ حالت (ورودی «انفجار حالت‌ها»)، ولی معمولاً خیلی کمتر. این همان کاری است که ابزارهای عبارت منظم (مثل lex) انجام می‌دهند.

    ورودی

    هر سطر یک یال [از، نماد، به] با 0 = a، 1 = b، 2 = ε؛ حالت شروع ۰ و accept حالت پذیرش است.