اتوماتا و زبان‌های صوری

نظریه اتوماتا و زبان‌های صوری به مطالعه ماشین‌های ایده‌آل با قدرت فزاینده و دسته‌های رشته‌ها یا زبان‌هایی می‌پردازد که هر یک می‌توانند آن‌ها را تشخیص دهند. این نظریه یک توصیف ریاضی دقیق از آنچه به عنوان یک الگو محسوب می‌شود و آنچه برای تشخیص آن لازم است، ارائه می‌دهد.

Definition

یک زبان صوری مجموعه‌ای از رشته‌های متناهی بر روی یک الفبای ثابت است، و یک اتوماتا یک دستگاه محاسباتی انتزاعی است که محاسبات پذیرنده آن چنین زبانی را تعریف می‌کند؛ این حوزه زبان‌ها را بر اساس ساده‌ترین نوع اتوماتا یا گرامری که آن‌ها را تولید یا تشخیص می‌دهد، طبقه‌بندی می‌کند.

Scope

این حوزه شامل اتوماتای متناهی و زبان‌های منظم، اتوماتای پشته‌ای و زبان‌های مستقل از متن، سلسله‌مراتب چامسکی که گرامرها را به مدل‌های ماشین مرتبط می‌کند، ویژگی‌های بستاری و تصمیم‌پذیری کلاس‌های زبان، و اتوماتا‌هایی که کلمات و درختان نامتناهی را پردازش می‌کنند، به همراه مشخصه‌های جبری و منطقی مرتبط با آن‌ها می‌شود.

Sub-topics

• اتوماتا بر روی اشیاء نامتناهی
• زبان‌های مستقل از متن و اتوماتای پشته‌ای
• اتوماتای متناهی و زبان‌های منظم
• سلسله مراتب چامسکی

Core questions

• کدام زبان‌ها را یک ماشین با حافظه متناهی می‌تواند تشخیص دهد و کدام‌ها را نمی‌تواند؟
• گرامرها و مدل‌های ماشین چگونه در سطوح سلسله‌مراتب چامسکی با یکدیگر مطابقت دارند؟
• کدام سؤالات درباره یک کلاس زبان، مانند تهی بودن یا هم‌ارزی، به صورت الگوریتمی تصمیم‌پذیر هستند؟
• اتوماتا چگونه به کلمات و درختان نامتناهی گسترش می‌یابند و چرا این موضوع برای تأیید اهمیت دارد؟

Key theories

هم‌ارزی اتوماتای متناهی قطعی و غیرقطعی

هر اتوماتای متناهی غیرقطعی را می‌توان با ساختار زیرمجموعه به یک اتوماتای قطعی تبدیل کرد که همان زبان را می‌پذیرد، بنابراین غیرقطعی بودن قدرت تشخیص بیشتری در سطح حالت متناهی اضافه نمی‌کند، اگرچه می‌تواند به صورت نمایی مختصرتر باشد.

قضیه کلینی

زبان‌های تشخیص داده شده توسط اتوماتای متناهی دقیقاً همان زبان‌های منظمی هستند که توسط عبارات منظم توصیف می‌شوند، و دیدگاه‌های ماشینی، جبری و گرامری ساده‌ترین کلاس زبان را به هم پیوند می‌دهد.

سلسله‌مراتب چامسکی

زبان‌های منظم، مستقل از متن، وابسته به متن و بازگشتی شمارش‌پذیر یک زنجیره شمول دقیق را تشکیل می‌دهند، که هر سطح با یک نوع گرامر و یک مدل اتوماتا با ساختار حافظه متناظر مطابقت دارد.

Clinical relevance

اتوماتای متناهی و عبارات منظم، تحلیل واژگانی را در کامپایلرها، جستجوی متن و مشخصات پروتکل‌ها تقویت می‌کنند، در حالی که گرامرهای مستقل از متن زیربنای تجزیه زبان‌های برنامه‌نویسی هستند؛ اتوماتا بر روی اشیاء نامتناهی هسته الگوریتمی بررسی مدل (model checking) را تشکیل می‌دهند، جایی که یک سیستم در برابر یک مشخصه منطق زمانی تأیید می‌شود.

History

مدل‌های حالت متناهی از شبکه‌های عصبی مک‌کالک و پیتس در دهه ۱۹۴۰ پدید آمدند و توسط کلینی در حدود سال ۱۹۵۱ به شکل نظریه زبان درآمدند. رابین و اسکات اتوماتای غیرقطعی را در سال ۱۹۵۹ معرفی کردند، در حالی که گرامرهای چامسکی از اواخر دهه ۱۹۵۰ کلاس‌های زبان را در سلسله‌مراتبی سازماندهی کردند که هنوز هم ساختار این موضوع را تشکیل می‌دهد.

Key figures

• Stephen Kleene
• Michael Rabin
• Dana Scott
• Noam Chomsky

Seminal works

• rabinScott1959
• sipser2013
• hopcroft2006

Frequently asked questions

چرا یک اتوماتای متناهی نمی‌تواند پرانتزهای متعادل را تشخیص دهد؟

تشخیص تو در تویی با عمق دلخواه نیاز به شمارش تعداد پرانتزهای باز دارد که هنوز تطبیق نیافته‌اند، که این تعداد می‌تواند از هر تعداد حالت ثابت فراتر رود. یک اتوماتای متناهی تنها حافظه محدود دارد، بنابراین این قابلیت شمارش یک سطح بالاتر، با اتوماتای پشته‌ای و زبان‌های مستقل از متن قرار می‌گیرد.

فایده عملی نظریه زبان‌های صوری چیست؟

این نظریه به مهندسان می‌گوید که یک ابزار معین چه الگوهایی را می‌تواند بیان کند. عبارات منظم برای توکن‌ها کافی هستند اما برای ساختار تو در تو نه، به همین دلیل کامپایلرها کار را بین یک تحلیل‌گر واژگانی منظم و یک تجزیه‌کننده مستقل از متن تقسیم می‌کنند، و به همین دلیل ابزارهای تأیید بر اتوماتا بر روی کلمات نامتناهی تکیه می‌کنند.