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

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

Definition

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

Scope

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

Core questions

• چگونه محدودیت‌ها در قوانین گرامری به محدودیت‌ها در حافظه و قدرت محاسباتی تبدیل می‌شوند؟
• چرا هر سطح از سلسله مراتب به طور دقیق در سطح بعدی گنجانده شده است؟
• کدام مدل اتوماتون با هر نوع گرامر مطابقت دارد؟
• چگونه ویژگی‌های تصمیم‌پذیری و بستار با حرکت به سمت بالای سلسله مراتب تغییر می‌کنند؟

Key theories

تطابق گرامر-ماشین

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

شمول دقیق کلاس‌های زبان

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

Clinical relevance

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

History

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

Key figures

• Noam Chomsky
• Marcel-Paul Schützenberger
• John Myhill

Seminal works

• hopcroft2006
• sipser2013

Frequently asked questions

چهار سطح سلسله مراتب چامسکی کدامند؟

از کمترین تا قدرتمندترین آنها عبارتند از زبان‌های منظم (نوع ۳)، زبان‌های مستقل از متن (نوع ۲)، زبان‌های حساس به متن (نوع ۱)، و زبان‌های بازگشتی شمارش‌پذیر (نوع ۰). هر سطح محدودیت‌ها را بر قوانین گرامری کاهش می‌دهد و با ماشینی با حافظه بیشتر مطابقت دارد.

آیا زبان طبیعی توسط سلسله مراتب چامسکی پوشش داده می‌شود؟

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