وراثت چامسکی

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

وراثت چامسکی (به انگلیسی: Chomsky_hierarchy)‏نوعی وراثت محدودکننده برای کلاسهای دستور زبان قراردادی است که زبان‌های قراردادی را تولید می‌کند. این وراثت در سال ۱۹۵۶ توسط نوام چامسکی معرفی شد.

وراثت چامسکی از ۴ نوع تشکیل شده‌است:

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

دستور زبان نوع ۱: گرامرهای حساس به متن که زبان‌های حساس به متن را تولید می‌کند. زبان‌های ایجاد شده توسط linear bounded automata شناسایی و مورد پذیرش واقع می‌شوند. از نمونه‌های طبیعی اینگونه زبان‌ها می‌توان به زبان‌های هلندی و آلمانی اشاره کرد. البته همه زبان‌ها اینگونه نیستند و بیشتر در زبان‌شناسی کامپیوتر محور است که ساختارهایی از این نوع وجود دارد. نوع ۱ قواعدی به فرم زیر دارند:

\alpha , \beta \in V^* B \ne \epsilon ; A,B \in N ; \alpha A \beta \to \alpha B \beta ;

یا

S \to \epsilon S \in N ;

Sعضو ابتدایی است و \epsilon رشته خالی است.

دستور زبان نوع ۲: دستور زبان‌های مستقل از متن که زبان‌های مستقل از متن را تولید می‌کند، زبان‌های ایجاد شده توسط push-down automata شناسایی و مورد پذیرش واقع می‌شوند. نحو ترکیب رشته‌ها و همچنین درخت ساختاری در اکثر زبان‌های طبیعی تا حد خیلی خوبی بر اساس این نوع دستور زبان قابل تعریف است. نوع ۲ قواعدی به فرم زیر دارند:

A \in N , B \in V^* A \to B ;

بیشتر زبان‌های برنامه نویسی دارای این نوع دستور زبان می‌باشند.

تعدادی صورت هنجار وجود دارد که برای مثال می‌توان از صورت هنجار چامسکی یا صورت هنجار گریباخ نام برد که توسط اینان می‌توان CFG را تبدیل کرد؛ که اینها بهینه سازی مناسبی برای سبک خاصی از پردازش‌ها می‌باشند.

دستور زبان نوع ۳: دستور زبان‌های با قاعده که زبان‌های با قاعده را تولید می‌کند، زبان‌های ایجاد شده توسط finite state automata شناسایی و مورد پذیرش واقع می‌شوند. ساختارهای ریخت‌شناسی و احتمالا اکثر دیالوگ‌های غیر رسمی گفته شده، قابل تعریف با دستور زبان باقاعده می‌باشد. دو نوع دستور زبان با قاعده وجود دارد:

۱- راست با قاعده:

A \to \gamma A \to \gamma B ;

که در این نوع قاعده، زبان از سمت راست انشعاب پیدا می‌کند.

۲- چپ با قاعده:

A \to \gamma A \to B \gamma ;

که در این نوع قاعده، زبان از سمت چپ انشعاب پیدا می‌کند.

منابع [ویرایش]

پیوند به بیرون [ویرایش]

برگرفته از «http://fa.wikipedia.org/w/index.php?title=وراثت_چامسکی&oldid=9637752»