AlgoVerse

تبدیل گرامر منظم به ماشین حالت

از یک گرامر منظم (قاعده‌هایی مثل A → aB) ماشین حالت معادل می‌سازد: هر ناپایانه یک حالت و هر قاعده یک یال؛ بعد رشته‌ای را روی آن امتحان می‌کند.

در گرامر منظم (خطی راست) هر قاعده یا A → aB است (نماد a و رفتن به ناپایانه‌ی B) یا A → a (نماد آخر). این دقیقاً شکل یک ماشین حالت است:

ادامه‌ی توضیح ↓
ورودی:
rules="S=aS|bA;A=bA…" · w="aabb"خروجی PDF

S → aS | bA، A → bA | b: رشته‌هایی با چند a و بعد دست‌کم دو b. aabb در زبان هست.

  1. def grammar_to_automaton(rules, w):
  2. # rules like "S=aA|b;A=bS": capital letters are nonterminals, small letters terminals.
  3. # Each rule A → aB becomes an edge A --a--> B, and A → a an edge A --a--> F (the final state).
  4. states = []
  5. edges = []
  6. for rule in rules.split(";"):
  7. if "=" not in rule:
  8. return None
  9. lhs, rhs = rule.split("=")
  10. if lhs not in states:
  11. states.append(lhs)
  12. for option in rhs.split("|"):
  13. target = option[1] if len(option) > 1 else "F"
  14. edges.append([lhs, option[0], target])
  15. states.append("F")
  16. # Run the automaton on w, keeping every state it could be in.
  17. current = [states[0]]
  18. for i in range(len(w)):
  19. reached = set()
  20. for s, a, t in edges:
  21. if s in current and a == w[i]:
  22. reached.add(t)
  23. current = sorted(reached)
  24. accepted = "F" in current
  25. return accepted

ناوردا: رشته‌ی x از ناپایانه‌ی A مشتق می‌شود اگر و فقط اگر ماشین از حالت A با خواندن x به F برسد.

شروع اجرا

0123
aabb
states—
current—

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

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

rules'S=aS|bA;A=bA|b'
w'aabb'

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

Call stack

  1. grammar_to_automaton()خط 1
گام ۱ از ۸۶
خط سیاه = production, read · خط نارنجی = گام کلیدیnonterminal: 0/2 · production: 0/4 · read: 0/4 · verdict: 0/1
    توضیح

    ایده

    در گرامر منظم (خطی راست) هر قاعده یا A → aB است (نماد a و رفتن به ناپایانه‌ی B) یا A → a (نماد آخر). این دقیقاً شکل یک ماشین حالت است:

    • هر ناپایانه یک حالت؛ نماد شروع، حالت شروع است.
    • A → aB یعنی یال A --a--> B.
    • A → a یعنی یال A --a--> F که F حالت پایانی تازه است.

    رشته‌ای در زبان گرامر است اگر و فقط اگر ماشین با خواندنش از حالت شروع به F برسد. پس گرامرهای منظم و ماشین‌های حالت متناهی دقیقاً یک دسته زبان را توصیف می‌کنند.

    ورودی

    قاعده‌ها با ; جدا می‌شوند و گزینه‌ها با |: مثلاً S=aS|bA;A=bA|b. حرف بزرگ ناپایانه و حرف کوچک پایانه است. ماشین ممکن است ناقطعی باشد، پس هم‌زمان مجموعه‌ای از حالت‌ها دنبال می‌شود.