پذیرنده متناهی معین

اتوماتون تعیین‌پذیر متناهی (Deterministic Finite Automaton - DFA) به یک پنج‌تائی ${\displaystyle M=(Q,\mathrm{\Sigma },\delta ,q_0,F)}$

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

می‌باشد. فرض کنید w = a₁a₂ … a_n رشته‌ای از الفبای ${\displaystyle \mathrm{\Sigma }}$

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

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

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

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

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

	0	1
S1	S2	S1
S2	S1	S2

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

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

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

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

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

بعلاوه، یک اجرا (run) می‌تواند به عنوان یک دنباله از ترکیب توابع انتقال با خودشان دیده شود. نماد ورودی ${\displaystyle a\in \mathrm{\Sigma }}$