پذیرنده متناهی معین
From Wikipedia, the free encyclopedia
در نظریه اتوماتا، شاخهای از علوم کامپیوتر نظری، ماشینهای تعیینپذیر حالات متناهی (Deterministic finite-state machine) به آن دسته از ماشینهای حالات متناهی گفته میشود که رشته متناهی از سمبلها را میپذیرد یا رد میکند و برای هر رشته ورودی تنها محاسباتی یکتا از ماشین اتوماتا را تولید میکند. در واقع 'تعیینپذیری' در این ماشینها به یکتایی محاسبات برمیگردد. در جستجوی سادهترین روشها برای نمایش ماشینهای حالت متناهی، مککالک (McCulloch) و پیتس (Pitts) در میان اولین محققانی بودند که مفاهیم و ایدههایی شبیه به ماشینهای اتوماتای محدود را در سال ۱۹۴۳ معرفی کردند.
برای تأییدپذیری کامل این مقاله به منابع بیشتری نیاز است. (فوریه ۲۰۱۵) |
این مقاله نیازمند ویکیسازی است. لطفاً با توجه به راهنمای ویرایش و شیوهنامه، محتوای آن را بهبود بخشید. (فوریه ۲۰۱۵) |
شکل سمت چپ، یک ماشین تعینپذیر حالات متناهی را با استفاده از نمودار حالتها نشان میدهد. در این ماشین اتوماتا، سه حالت S0، S1 و S2 وجود دارند (که در تصویر با دایره نشان داده شدهاند). ماشین اتوماتا دنبالهای از ۰ها و ۱ها را به عنوان ورودی دریافت میکند. برای هر حالت، به ازای هر یک از ۰ و ۱، یک بردار انتقال موجود است که به حالت بعد راهنمایی میکند. تا زمانی که یک نماد را میخوانیم، یک DFA به صورت تعیین پذیر و قطعی با دنبال کردن بردارهای انتقال از حالتی به حالت دیگر حرکت میکند. برای مثال، اگر ماشین اتوماتا در حالت S0 قرار دارد و نماد ورودی نیز ۱ است، به صورت قطعی به حالت S1 خواهد رفت. یک DFA دارای یک حالت آغازین است (با فلشی که از هیچ کجا به آن وارد میشود، نشان داده میشود) که محاسبات در آن آغاز میشوند، و یک مجموعه از حالات نهایی (با دایره دوخطه نشان داده میشوند) که کمک میکند زمانی را که محاسبات موفق شدهاست را تعریف کنیم. یک DFA به عنوان یک مفهوم ریاضی مطلق تعریف شدهاست، اما با توجه به ذات نعیینپذیر DFA، قابل پیادهسازی در سختافزار و نرمافزار برای حل مسائلی خاص و مختلف است. برای مثال یک DFA میتواند یک نرمافزار را که تصمیم میگیرد که آیا ورودی کاربر (برای مثال) یک آدرس ایمیل معتبر است یا نه، مدل کند. DFAها دقیقاً مجموعه زبانهای منظم را که، به غیر از موارد دیگر، برای انجام آنالیزهای واژگانی و تطبیقهای الگویی مفید هستند، میپذیرند. همچنین DFAها میتوانند از طریق ساخت مجموعه توانی از ماشینهای تعینناپذیر حالات متناهی ساخته شوند.