ماشین تعیین‌پذیر حالات متناهی

در نظریه اتوماتا، شاخه‌ای از علوم کامپیوتر نظری، ماشین‌های تعیین‌پذیر حالات متناهی (Deterministic finite-state machine) به آن دسته از ماشین‌های حالات متناهی اطلاق می‌شود که رشته متناهی از سمبل‌ها را می‌پذیرد یا رد می‌کند و برای هر رشته ورودی تنها محاسباتی یکتا از ماشین اتوماتا را تولید می‌کند. در واقع 'تعیین‌پذیری' در این ماشین‌ها به یکتایی محاسبات بر‌می‌گردد. در جستجوی ساده‌ترین روش‌ها برای نمایش ماشین‌های حالت متناهی، مک‌کالک (McCulloch) و پیتس (Pitts) در میان اولین محققانی بودند که مفاهیم و ایده‌هایی شبیه به ماشین‌های اتوماتای محدود را در سال 1943 معرفی کردند.

مثالی از یک ماشین تعین‌پذیر حالات متناهی که تنها اعدادی باینری را که مضربی از 3 باشند، می‌پذیرد. در این‌جا حالت S₀ نیز هم حالت آغازین و هم حالت نهایی است.

شکل سمت راست، یک ماشین تعین‌پذیر حالات متناهی را با استفاده از نمودار حالت ها نشان می دهد. در این ماشین اتوماتا، سه حالت S₀، S₁ و S₂ وجود دارند (که در تصویر با دایره نشان داده شده‌اند). ماشین اتوماتا دنباله ای از 0ها و 1ها را به عنوان ورودی دریافت می‌کند. برای هر حالت، به ازای هر یک از 0 و 1، یک بردار انتقال موجود است که به حالت بعد راهنمایی می‌کند. تا زمانی که یک نماد را می‌خوانیم، یک DFA به صورت تعیین پذیر و قطعی با دنبال کردن بردار‌های انتقال از حالتی به حالت دیگر حرکت می کند. برای مثال، اگر ماشین اتوماتا در حالت S₀ قرار دارد و نماد ورودی نیز 1 است، به صورت قطعی به حالت S₁ خواهد رفت. یک DFA دارای یک حالت آغازین است (با فلشی که از هیچ کجا به آن وارد می‌شود، نشان داده می‌شود)که محاسبات در آن آغاز می‌شوند، و یک مجموعه از حالات نهایی (با دایره دو‌خطه نشان داده می‌شوند) که کمک می‌کند زمانی را که محاسبات موفق شده است را تعریف کنیم. یک DFA به عنوان یک مفهوم ریاضی مطلق تعریف شده است، اما با توجه به ذات نعیین‌پذیر DFA، قابل پیاده‌سازی در سخت افزار و نرم افزار برای حل مسائلی خاص و مختلف است. برای مثال یک DFA می‌تواند یک نرم افزار را که تصمیم می‌گیرد که آیا ورودی کاربر (برای مثال) یک آدرس ایمیل معتبر است یا نه، مدل کند. DFAها دقیقا مجموعه زبان‌های منظم را که، به غیر از موراد دیگر، برای انجام آنالیزهای واژگانی و تطبیق‌های الگویی مفید هستند، می پذیرند. همچنین DFA‌ها می‌توانند از طریق ساخت مجموعه توانی از ماشین‌های تعین‌ناپذیر حالات متناهی ساخته شوند.

تعریف رسمی

اتوماتون تعیین‌پذیر متناهی (Deterministic Finite Automaton - DFA) به یک پنج‌تائی $M = (Q, \Sigma, \delta, q_0, F) \!$ گفته می‌شود، که شامل:

• $Q \!$ یک مجموعهٔ متناهی از حالات
• $\Sigma \!$ یک مجموعهٔ متناهی از نمادهای ورودی موسوم به الفبا
• $q_0 \!$ حالت آغازین (q₀ ∈ Q)
• $F \!$ مجموعهٔ حالات نهائی یا مجموعهٔ حالات مورد قبول (F ⊆ Q)
• $\delta \!$ تابع انتقال (δ : Q × Σ → Q)

می باشد. فرض کنید w = a₁a₂ ... a_n رشته‌ای از الفبای $\Sigma \!$ باشد.در این صورت رشته w توسط اتوماتون M پدیرفته می‌شود، اگر دنباله‌ای از حالات r₀,r₁, ..., r_n در Q با شرایط زیر وجود داشته باشند:

1. r₀ = q₀
2. r_i+1 = δ(r_i, a_i+1), for i = 0, ..., n−1
3. r_n ∈ F.

به عبارت دیگر، شرط اول بیان می‌کند که ماشین با همان حالت آغازین q₀ شروع به محاسبه کند. شرط دوم بیان می‌کند که بر اساس هر یک از کاراکترهای رشته w داده شده، ماشین از حالتی به حالت دیگر طبق تابع انتقال δ انتقال خواهد یافت. و شرط آخر بیان می‌کند که ماشین w را می‌پذیرد، اگر آخرین ورودی w باعث توقف ماشین در یکی از حالات پایانی شود. در غیر این صورت، گفته می‌شود که اتوماتون رشته را رد کرده است. مجموعه همه رشته‌هایی که M می‌پذیرد، زبانیست که در M صدق می‌کند و این زبان با (L(M نشان داده می‌شود. ماشین تعین‌پذیر متناهی که حالت پایانی و آغازین ندارد به عنوان سیستم انتقال و یا شبه‌اتوماتون شناخته می‌شود. برای آشنایی بیشتر با تعریف رسمی نظریه اتوماتا را ببینید.

مثال‌ها

مثال زیر، DFAی M با الفبای باینری است که ورودی‌هایی را که شامل تعداد زوجی 0 هستند را می‌پذیرد.

نمودار حالات M

(M = (Q, Σ, δ, q₀, F که

• {Q = {S₁, S₂,
• {Σ = {0, 1,
• q₀ = S₁,
• {F = {S₁, و
• δ که با جدول انتقال حالت زیر تعریف می‌شود:

	0	1
S1	S2	S1
S2	S1	S2

حالت S₁ نشان‌دهنده این است که تاکنون تعداد زوجی 0 در ورودی بوده است. در حالی که S₂ حاکی از تعداد فردی 0 است. یک 1 در ورودی حالت اتوماتون را تغییر نمی‌دهد. زمانی که ورودی پایان یابد، حالت اتوماتون نشان‌دهنده آن خواهد بود که آیا ورودی دارای تعداد زوجی 0 است یا نه. اگر ورودی شامل تعداد زوجی 0 باشد، M در حالت S₁ که حالتی پایانی است، پایان خواهد یافت و بنابراین رشته ورودی پذیرفته خواهد شد. زبانی که در M صدق می‌کند یک زبان منظم است که با عبارت منظم *((*1)0(*1)0)*1 نشان داده می‌شود. "*" همان ستاره کلینی است؛ برای مثال *1 نشان‌دهنده هر تعداد غیرمنفی (شاید صفر عدد) از نماد 1 است.

ویژگی های بستاری

اگر زبانِ DFAی حاصل از اعمال عملیاتی بر DFAها قبل تشخیص با یک DFA باشد، گفته می شود که DFAها تحت آن عملیات بسته هستند. DFAها تحت عملیات زیر بسته هستند:

• اجتماع
• اشتراک
• الحاق
• ستاره کلین
• معکوس سازی
• Negation
• Init
• Quotient

ازآن‌جایی‌که DFAها هم‌ارز با ماشین‌های تعیین‌ناپذیر متناهی NFA هستند، ویژگی‌های بستاری بالا با استفاده از ویژگی‌های بستاری NFA ها اثبات می‌شوند.

شیوه‌های پذیرنده و تولیدکننده

يک DFA که نماينده يک زبان منظم است، مي‌تواند هم به عنوان پذيرنده، براي تصديق عضويت يک رشته ورودي در زبان، و هم به عنوان توليدکننده، براي توليد ليستي از رشته‌هاي زبان، استفاده شود. در حالت پذيرنده، يک رشته ورودي فراهم شده است که اتوماتون مي‌تواند آن را از چپ به راست، و هر بار يک نماد را بخواند. محاسبات از حالت آغازين شروع شده و با خواندن اولين نماد از رشته ورودي و دنبال کردن انتقال حالات طبق نمادها پيش مي‌رود. سيستم به خواندن نمادها و دنبال کردن انتقال‌ها تا زماني که ديگر هيچ نمادي در ورودي باقي نمانده باشد، که نشان‌دهنده پايان محاسبات است، ادامه مي‌دهد. اگر پس از پايان يافتن پردازش همه نمادهاي ورودي، سيستم در حالت پاياني باشد، خواهيم دانست که که رشته ورودي در واقع جزئي از زبان است، و گفته مي‌شود که پذيرفته شده است؛ درغيراين‌صورت جزئي از زبان نبوده و پذيرفته نشده است. حالت توليدکننده هم شبيه است؛ به غير از اين که علاوه‌بر تعيين اعتبار يک رشته ورودي، هدف آن تعين همه رشته هاي موجود در زبان است. به جاي دنبال کردن يک انتقالِ خروجي از هر حالت، همه آن‌ها را دنبال مي‌کند. و در عمل اين با يک سري عمليات موازي سنگين (داشتن يک برنامه که هر بار با تصميم گيري مواجه مي‌شود به دو يا بيشتر پردازه انشعاب مي‌يابد) و يا از طريق محاسبات بازگشتي به انجام مي‌رسد. مانند قبل، محاسبات از حالت آغازين شروع شده و سپس با دنبال کردن هر يک از انتقال‌هاي دردسترس پيش مي‌رود، با آگاهي از اين که کدام يک از شاخه‌ها انتخاب شده است. هر بار که اتوماتون خودش را در حالت پاياني بيابد، درمي‌يابد که دنباله‌اي از شاخه‌هايي که انتخاب شده است، يک رشته مورد قبول از زبان را تشکيل مي‌دهد و آن رشته را به ليستي که در حال توليد آن است، اضافه مي‌کند. اگر زباني که اين اتوماتون شرح مي‌دهد، نامتناهي باشد (يعني شامل تعداد نامتناهي از اعداد يا رشته‌ها باشد، مثلا همه رشته‌هاي دودويي با تعداد زوجي صفر)؛ محاسبات هرگز متوقف نخواهد شد. مسلم است که زبان‌هاي منظم، به‌طورکلي، نامتناهي هستند، اتوماتا در حالت توليد کننده گرايش بيشتر به ساخت نظري دارد.

DFA به عنوان انتقال مونوئید یا تکوار

بعلاوه، یک اجرا (run) می‌تواند به عنوان یک دنباله از ترکیب توابع انتقال با خودشان دیده شود. نماد ورودی $a\in\Sigma$ داده شده است، امکان دارد شخصی تابع انتقال را به صورت $\delta_a:Q\rightarrow Q$، با استفاده حیله ساده currying بنویسد که به صورت $\delta(q,a)=\delta_a(q)$ برای هر $q \in Q$ نوشته می‌شود. بدین صورت، تابع انتقال می‌تواند به صورت ساده‌تری دیده بشود: این تنها چیزیست که روی حالتی از Q "عمل می‌کند"، و به حالت دیگر می‌رود. ممکن است بدین صورت در نظر گرفته شود که نتیجه ترکیب توابعی است که مکرراً به توابع مختلف $\delta_a$, $\delta_b$ اعمال می‌شوند، و قس على هذا. با استفاده از این مفهوم $\widehat\delta:Q \times \Sigma^{\star} \rightarrow Q$ را تعریف می کنیم. دو حرف $a,b\in \Sigma$ داده شده است، ممکن است شخصی تابع جدید $\widehat\delta$ را با تکیه کردن بر $\widehat\delta_{ab}=\delta_a \circ \delta_b$ تعریف کند، که $\circ$ نشان‌دهنده ترکیب توابع است. به وضوح، این فرآیند می‌تواند به صورت بازگشتی ادامه داده شود.بنابراین تعریف بازگشتی ذیل را داریم: $\widehat\delta ( q, \epsilon ) = q.$ که $\epsilon$ رشته تهی است و: $\widehat\delta ( q, wa ) = \delta_a(\widehat\delta ( q, w )).$ که $w \in \Sigma ^*, a \in \Sigma$ و $q \in Q$. $\widehat\delta$ برای هر $w\in\Sigma^*$ تعریف شده است. ترکیب مکرر توابع یک مونوئید یا تکوار را به وجود می‌آورد. برای تابع انتقال، این مونوئید به عنوان انتقال مونوئید و یا گاهی شبه‌گروه تغییر شکل شناخته می شود. همچنین این ساخت می‌تواند برعکس شود: $\widehat\delta$ داده شده است، شخصی می تواند $\delta$ را دوباره‌سازی کند، و بنابراین هر دو توصیف معادلند.

منابع

• Sudkamp, T. A., An Introduction to the Theory of Computer Science, Languages and Machines, 3rd ed., Pearson Education, Inc., 2006. ISBN 0-321-32221-5 [۱]