ماشین حالت متناهی (تشخیص دنباله)
یک ماشین سه‌حالته رشته‌ی دودویی را بیت به بیت می‌خواند و تشخیص می‌دهد عددش بر ۳ بخش‌پذیر است یا نه؛ بدون نگه داشتن خود عدد.
ماشین حالت متناهی فقط تعداد محدودی حالت دارد و با هر نماد ورودی، طبق جدول انتقال δ، از یک حالت به حالت دیگر می‌رود. اگر در پایان در یکی از حالت‌های پذیرش باشد، رشته پذیرفته می‌شود.
- زمان:
O(n) - حافظه:
O(1) - جانسون‌باو، فصل ۱۲
- گریمالدی، فصل ۶
۱۰۰۱۰ = ۱۸ بر ۳ بخش‌پذیر است؛ ماشین در حالت ۰ تمام می‌کند.
def multiple_of_three(s):# A machine with three states: the value read so far, mod 3. Reading bit b turns value v into 2v + b.delta = {0: {"0": 0, "1": 1}, 1: {"0": 2, "1": 0}, 2: {"0": 1, "1": 2}}table = [[q, delta[q]["0"], delta[q]["1"]] for q in range(3)] # rows: state, after 0, after 1state = 0for i in range(len(s)):state = delta[state][s[i]]accepted = state == 0return accepted
شروع اجرا
جدول هنوز خالی است.
متغیرهای محلی
نارنجی = در همین گام عوض شد
Call stack
- multiple_of_three()خط 1
توضیح
ایده
ماشین حالت متناهی فقط تعداد محدودی حالت دارد و با هر نماد ورودی، طبق جدول انتقال δ، از یک حالت به حالت دیگر می‌رود. اگر در پایان در یکی از حالت‌های پذیرش باشد، رشته پذیرفته می‌شود.
سه حالت کافی است
اگر مقدار بیت‌های خوانده‌شده v باشد، خواندن بیت b آن را 2v + b می‌کند. برای بخش‌پذیری بر ۳ فقط v mod 3 مهم است:
v mod 3 = r ⇒ (2v + b) mod 3 = (2r + b) mod 3
پس سه حالت 0، 1 و 2 بس است، هر قدر هم عدد بزرگ باشد. حالت 0 هم شروع است و هم پذیرش.
در trace به چه چیزی نگاه کنی
- جدول انتقال‌های ماشین است (هر سطر یک حالت)؛ کارت
stateحالت فعلی را با خواندن هر بیت نشان می‌دهد.