موضوع مقاله: پذیرنده متناهی معین | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # پذیرنده متناهی معین | مقدمه: در جستجوی ساده‌ترین روش‌ها برای نمایش ماشین‌های حالت متناهی، مک‌کالک (McCulloch) و پیتس (Pitts) در میان اولین محققانی بودند که مفاهیم و ایده‌هایی شبیه به ماشین‌های اتوماتای محدود را در سال ۱۹۴۳ معرفی کردند. | ## بخش 1: پذیرنده متناهی معین | شکل سمت چپ، یک ماشین تعین‌پذیر حالات متناهی را با استفاده از نمودار حالت‌ها نشان می‌دهد. در این ماشین اتوماتا، سه حالت S0، S1 و S2 وجود دارند (که در تصویر با دایره نشان داده شده‌اند). برای هر حالت، به ازای هر یک از ۰ و ۱، یک بردار انتقال موجود است که به حالت بعد راهنمایی می‌کند. تا زمانی که یک نماد را می‌خوانیم، یک DFA به صورت تعیین پذیر و قطعی با دنبال کردن بردارهای انتقال از حالتی به حالت دیگر حرکت می‌کند. برای مثال، اگر ماشین اتوماتا در حالت S0 قرار دارد و نماد ورودی نیز ۱ است، به صورت قطعی به حالت S1 خواهد رفت. یک DFA دارای یک حالت آغازین است (با فلشی که از هیچ کجا به آن وارد می‌شود، نشان داده می‌شود) که محاسبات در آن آغاز می‌شوند، و یک مجموعه از حالات نهایی (با دایره دوخطه نشان داده می‌شوند) که کمک می‌کند زمانی را که محاسبات موفق شده‌است را تعریف کنیم. یک DFA به عنوان یک مفهوم ریاضی مطلق تعریف شده‌است، اما با توجه به ذات نعیین‌پذیر DFA، قابل پیاده‌سازی در سخت‌افزار و نرم‌افزار برای حل مسائلی خاص و مختلف است. برای مثال یک DFA می‌تواند یک نرم‌افزار را که تصمیم می‌گیرد که آیا ورودی کاربر (برای مثال) یک آدرس ایمیل معتبر است یا نه، مدل کند. DFAها دقیقاً مجموعه زبان‌های منظم را که، به غیر از موارد دیگر، برای انجام آنالیزهای واژگانی و تطبیق‌های الگویی مفید هستند، می‌پذیرند. همچنین DFAها می‌توانند از طریق ساخت مجموعه توانی از ماشین‌های تعین‌ناپذیر حالات متناهی ساخته شوند. به عبارت دیگر، شرط اول بیان می‌کند که ماشین با همان حالت آغازین q0 شروع به محاسبه کند. شرط دوم بیان می‌کند که بر اساس هر یک از کاراکترهای رشته w داده شده، ماشین از حالتی به حالت دیگر طبق تابع انتقال δ انتقال خواهد یافت؛ و شرط آخر بیان می‌کند که ماشین w را می‌پذیرد، اگر آخرین ورودی w باعث توقف ماشین در یکی از حالات پایانی شود. مجموعه همه رشته‌هایی که M می‌پذیرد، زبانیست که در M صدق می‌کند و این زبان با (L(M نشان داده می‌شود. | ## بخش 2: پذیرنده متناهی معین | ماشین تعین‌پذیر متناهی که حالت پایانی و آغازین ندارد به عنوان سیستم انتقال یا شبه‌اتوماتون شناخته می‌شود. مثال‌ها مثال زیر، DFAی M با الفبای باینری است که ورودی‌هایی را که شامل تعداد زوجی ۰ هستند را می‌پذیرد. زمانی که ورودی پایان یابد، حالت اتوماتون نشان‌دهنده آن خواهد بود که آیا ورودی دارای تعداد زوجی ۰ است یا نه. اگر ورودی شامل تعداد زوجی ۰ باشد، M در حالت S1 که حالتی پایانی است، پایان خواهد یافت و بنابراین رشته ورودی پذیرفته خواهد شد. زبانی که در M صدق می‌کند یک زبان منظم است که با عبارت منظم * *۱)۰(*۱)۰)*۱ نشان داده می‌شود. "*" همان ستاره کلینی است؛ برای مثال *۱ نشان‌دهنده هر تعداد نامنفی (شاید صفر عدد) از نماد ۱ است. شیوه‌های پذیرنده و تولیدکننده یک DFA که نماینده یک زبان منظم است، می‌تواند هم به عنوان پذیرنده، برای تصدیق عضویت یک رشته ورودی در زبان، و هم به عنوان تولیدکننده، برای تولید لیستی از رشته‌های زبان، استفاده شود. در حالت پذیرنده، یک رشته ورودی فراهم شده است که اتوماتون می‌تواند آن را از چپ به راست، و هر بار یک نماد را بخواند. محاسبات از حالت آغازین شروع شده و با خواندن اولین نماد از رشته ورودی و دنبال کردن انتقال حالات طبق نمادها پیش می‌رود. سیستم به خواندن نمادها و دنبال کردن انتقال‌ها تا زمانی که دیگر هیچ نمادی در ورودی باقی نمانده باشد، که نشان‌دهنده پایان محاسبات است، ادامه می‌دهد. اگر پس از پایان یافتن پردازش همه نمادهای ورودی، سیستم در حالت پایانی باشد، خواهیم دانست که که رشته ورودی در واقع جزئی از زبان است، و گفته می‌شود که پذیرفته شده است؛ درغیراین‌صورت جزئی از زبان نبوده و پذیرفته نشده است. حالت تولیدکننده هم شبیه است؛ به غیر از این که علاوه‌بر تعیین اعتبار یک رشته ورودی، هدف آن تعین همه رشته‌های موجود در زبان است. به جای دنبال کردن یک انتقالِ خروجی از هر حالت، همه آن‌ها را دنبال می‌کند؛ و در عمل این با یک سری عملیات موازی سنگین (داشتن یک برنامه که هر بار با تصمیم‌گیری مواجه می‌شود به دو یا بیشتر پردازه انشعاب می‌یابد) یا از طریق محاسبات بازگشتی به انجام می‌رسد. | ## بخش 3: پذیرنده متناهی معین | مانند قبل، محاسبات از حالت آغازین شروع شده و سپس با دنبال کردن هر یک از انتقال‌های دردسترس پیش می‌رود، با آگاهی از این که کدام یک از شاخه‌ها انتخاب شده است. هر بار که اتوماتون خودش را در حالت پایانی بیابد، درمی‌یابد که دنباله‌ای از شاخه‌هایی که انتخاب شده است، یک رشته مورد قبول از زبان را تشکیل می‌دهد و آن رشته را به لیستی که در حال تولید آن است، اضافه می‌کند. اگر زبانی که این اتوماتون شرح می‌دهد، نامتناهی باشد (یعنی شامل تعداد نامتناهی از اعداد یا رشته‌ها باشد، مثلاً همه رشته‌های دودویی با تعداد زوجی صفر)؛ محاسبات هرگز متوقف نخواهد شد. مسلم است که زبان‌های منظم، به‌طورکلی، نامتناهی هستند، اتوماتا در حالت تولیدکننده گرایش بیشتر به ساخت نظری دارد. DFA به عنوان انتقال مونوئید یا تکوار بعلاوه، یک اجرا (run) می‌تواند به عنوان یک دنباله از ترکیب توابع انتقال با خودشان دیده شود. نماد ورودی داده شده است، امکان دارد شخصی تابع انتقال را به صورت ، با استفاده حیله ساده currying بنویسد که به صورت برای هر نوشته می‌شود. بدین صورت، تابع انتقال می‌تواند به صورت ساده‌تری دیده بشود: این تنها چیزیست که روی حالتی از Q «عمل می‌کند»، و به حالت دیگر می‌رود. ممکن است بدین صورت در نظر گرفته شود که نتیجه ترکیب توابعی است که مکرراً به توابع مختلف , اعمال می‌شوند، و قس علی‌هذا. دو حرف داده شده است، ممکن است شخصی تابع جدید را با تکیه کردن بر تعریف کند، که نشان‌دهنده ترکیب توابع است. به وضوح، این فرایند می‌تواند به صورت بازگشتی ادامه داده شود؛ بنابراین تعریف بازگشتی ذیل را داریم: که رشته تهی است و: که و . برای تابع انتقال، این مونوئید به عنوان انتقال مونوئید یا گاهی شبه‌گروه تغییر شکل شناخته می‌شود. | ## جمع‌بندی | همچنین این ساخت می‌تواند برعکس شود: داده شده است، شخصی می‌تواند را دوباره‌سازی کند، و بنابراین هر دو توصیف معادلند.