اتوماتای متناهی و زبانهای منظم
اتوماتای متناهی سادهترین ماشینهای محاسباتی هستند که ورودی را نماد به نماد با استفاده از تعداد محدودی از حالتهای داخلی میخوانند و زبانهایی که آنها تشخیص میدهند دقیقاً زبانهای منظم هستند.
Definition
اتوماتای متناهی ماشینی است با مجموعهای متناهی از حالتها، تابع انتقال بر روی نمادهای ورودی، یک حالت شروع، و حالتهای پذیرش؛ این ماشین یک رشته را میپذیرد اگر خواندن رشته آن را از حالت شروع به یک حالت پذیرش برساند، و مجموعه رشتههای پذیرفته شده، زبان آن است.
Scope
این موضوع شامل اتوماتای متناهی قطعی و غیرقطعی، همارزی آنها از طریق ساختار زیرمجموعه، عبارات منظم و قضیه کلینی، قضیه مایهیل-نرود و کمینهسازی حالت، ویژگیهای بستاری زبانهای منظم، و لم پمپاژ است که برای اثبات نامنظم بودن برخی زبانها استفاده میشود.
Core questions
- چه زبانهایی را میتوان تنها با استفاده از مقدار ثابت و متناهی حافظه تشخیص داد؟
- چرا اتوماتای متناهی قطعی و غیرقطعی به یک اندازه قدرتمند هستند؟
- چگونه میتوان اثبات کرد که یک زبان خاص منظم نیست؟
- کوچکترین اتوماتای تشخیصدهنده یک زبان منظم مشخص چیست؟
Key theories
- ساختار زیرمجموعه
- هر اتوماتای متناهی غیرقطعی را میتوان توسط یک اتوماتای قطعی شبیهسازی کرد که حالتهای آن مجموعههایی از حالتهای اصلی هستند، که اثبات میکند این دو مدل دقیقاً زبانهای یکسانی را تشخیص میدهند.
- قضیه کلینی
- یک زبان توسط یک اتوماتای متناهی تشخیص داده میشود اگر و تنها اگر توسط یک عبارت منظم توصیف شود، که همارزی توصیفات ماشینی و جبری زبانهای منظم را برقرار میکند.
- قضیه مایهیل-نرود
- یک زبان دقیقاً زمانی منظم است که رابطه عدم تمایز رشتههای آن دارای تعداد متناهی کلاس باشد، و این کلاسها اتوماتای قطعی مینیمال منحصر به فرد برای آن زبان را تعیین میکنند.
Clinical relevance
اتوماتای متناهی موتور محرک پشت تطبیق عبارات منظم، اسکنرها و تحلیلگرهای لغوی در کامپایلرها، جستجو و جایگزینی در ویرایشگرهای متن، و تشخیص الگو در سیستمهای نفوذ شبکه هستند، جایی که تشخیص با حافظه محدود، پردازش را سریع و قابل پیشبینی میکند.
History
بر اساس مدل شبکههای عصبی مککالک و پیتس در سال ۱۹۴۳، کلینی رویدادهایی را که اتوماتای متناهی میتوانند نمایش دهند، در حدود سال ۱۹۵۱ مشخص کرد، و رابین و اسکات اتوماتای غیرقطعی و مسائل تصمیمگیری آنها را در سال ۱۹۵۹ رسمی کردند، کاری که بعدها با جایزه تورینگ به رسمیت شناخته شد.
Key figures
- Stephen Kleene
- Michael Rabin
- Dana Scott
- Anil Nerode
Related topics
Seminal works
- rabinScott1959
- sipser2013
Frequently asked questions
- چگونه نشان میدهید که یک زبان منظم نیست؟
- متداولترین ابزار، لم پمپاژ است که بیان میکند هر رشته به اندازه کافی طولانی در یک زبان منظم شامل یک زیررشته است که میتواند هر تعداد بار تکرار شود در حالی که در زبان باقی بماند. یافتن رشتهای که به این روش قابل پمپاژ نباشد، اثبات میکند که زبان منظم نیست؛ قضیه مایهیل-نرود با نشان دادن بینهایت پیشوند قابل تمایز، یک استدلال جایگزین ارائه میدهد.
- اگر اتوماتای غیرقطعی قدرتمندتر نیستند، چرا از آنها استفاده میشود؟
- آنها اغلب بسیار کوچکتر و آسانتر برای طراحی یا استخراج از یک عبارت منظم هستند. ساختار زیرمجموعه میتواند آنها را در صورت نیاز به فرم قطعی تبدیل کند، با هزینه احتمالی نمایی در تعداد حالتها، بنابراین غیرقطعی بودن یک ابزار مشخصسازی مناسب است تا افزایش قدرت تشخیص.