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

نظریه زبان‌های صوری و ماشین‌های انتزاعی که آن‌ها را تشخیص می‌دهند، واژگانی را برای توصیف میزان پیچیدگی یک الگوی زبانی و الگوریتم‌هایی که می‌توانند آن را پردازش کنند، فراهم می‌کند.

Definition

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

Scope

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

Core questions

• کدام اتوماتا با هر سطح از سلسله‌مراتب چامسکی مطابقت دارد؟
• زبان طبیعی در کجای این سلسله‌مراتب قرار می‌گیرد و چرا استدلال می‌شود که قدرت آن از مستقل از متن فراتر است؟
• بسته بودن یک کلاس زبان تحت یک عملگر به چه معناست و چرا این موضوع برای مهندسی اهمیت دارد؟

Key concepts

• زبان منظم
• گرامر مستقل از متن
• گرامر وابسته به متن
• اتوماتای حالت متناهی
• اتوماتای پشته‌ای
• ماشین تورینگ
• ویژگی‌های بستار
• وابستگی خفیف به متن

Key theories

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

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

تطابق گرامر-اتوماتا

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

History

مقاله چامسکی در سال ۱۹۵۶ سلسله‌مراتب را به عنوان بخشی از استدلالی معرفی کرد که مدل‌های حالت متناهی برای زبان طبیعی ناکافی هستند. دهه‌های بعدی، تطابق‌های اتوماتا را رسمی کردند، و زبان‌شناسان محاسباتی بعدها نشان دادند که زبان طبیعی حداکثر به قدرت «کمی وابسته به متن» نیاز دارد، که این امر به فرمالیسم‌های گرامری فراتر از مستقل از متن انگیزه داد.

Debates

آیا زبان طبیعی مستقل از متن است؟

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

Key figures

• Noam Chomsky
• John Hopcroft
• Jeffrey Ullman
• Stephen Kleene

Seminal works

• chomsky1956
• hopcroft2006

Frequently asked questions

تفاوت بین یک زبان منظم و یک زبان مستقل از متن چیست؟

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