وراثت چامسکی
وراثت چامسکی یا سلسله‌مراتب چامسکی یا سلسله‌مراتب چامسکی-شوتزنبرگر در زمینه‌های علوم کامپیوتر و زبان‌شناسی، به خصوص در زمینهٔ زبان‌های صوری، یک سلسله مراتب نگهدارندهٔ کلاس‌های دستور زبان صوری است. سلسله‌مراتب گرامرها توسط نوآم چامسکی در سال ۱۹۵۶ توصیف شده است. در نام گذاری این سلسله مراتب، از اسم مارسل-پل شوتزنبرگر نیز به پاس نقش اساسی وی در توسعهٔ نظریهٔ زبان‌های رسمی (زبان صوری)، استفاده شده است. سلسله‌مراتب چامسکی در اصل امکان درک و بکارگیری مدل علوم کامپیوتر را فراهم می‌کند. این مدل به برنامه‌نویس‌ها اجازه می‌دهد که اهداف زبان‌شناسی مفهوم‌دار را به صورت سیستماتیک به انجام برسانند.
دستور زبانی رسمی از این نوع، از یک مجموعه‌ای متناهی از قواعد تولید تشکیل شده است ("سمت چپ" formula_1 "سمت راست") که هر سمت آن، خود شامل رشته‌ای از نمادهای زیر می‌باشد:
گرامر رسمی یک زبان رسمی را تعریف (یا تولید) می‌کند، که مجموعه‌ای (معمولاً متناهی) از رشته‌هایی با طول متناهی از نمادها هستند، که ممکن است با اعمال قواعد تولید به رشته‌ای دیگر از نمادها که از ابتدا فقط حاوی نماد آغازین بوده‌اند، ساخته شوند. یک قاعده می‌تواند با جایگزین کردن یک رخداد از نمادها در سمت چپ قاعده با رخدادی که در سمت راست ظاهر می‌شود، به رشته‌ای از نمادها اعمال شود. رشته‌ای از کاربردهای قاعده را «اشتقاق» می‌خوانند. چنین گرامری زبان رسمی را تعریف می‌کند: همهٔ واژه‌هایی که تنها از نمادهای پایانه‌ای تشکیل شده باشند که با اشتقاقی از نماد آغازین، قابل دسترسی باشند. ناپایانهها معمولاً با حروف بزرگ، پایانه‌ها با حروف کوچک، و نماد آغازین با formula_2 نمایش داده می‌شوند، مثلاً گرامری با پایانه‌های formula_3 ، ناپایانه‌های formula_4، قواعد تولید:
و نماد آغازین formula_2، زبان همهٔ واژه‌هایی با شکل formula_26 را تعریف می‌کند (یعنی formula_27 نسخه از formula_28 و به دنبال آن formula_27 کپی از formula_15). مورد بعدی گرامر ساده‌تری است که زبان مشابهی را تعریف می‌کند: پایانه‌های formula_3، ناپایانهٔ formula_32، نماد آغازین formula_2 ، قواعد تولید
به عنوان مثالی دیگر، گرامری برای یک زیرمجموعهٔ سرگرمی از زبان انگلیسی، به صورت زیر داده شده است: پایانه‌های formula_39 ، ناپایانه‌های formula_40 ، قواعد تولید
و نماد آغازین formula_41 . مثالی از اشتقاق این است:
سایر رشته‌هایی که می‌توانند از این گرامر مشتق شوند "ideas hate greate linguists" و "ideas generate" هستند. این جملات بی‌معنی هستند، اما از لحاظ ساختاری صحیحند. جمله‌ای که از لحاظ ساختاری نادرست باشد، مثل "ideas ideas great hate"، نمی‌تواند از گرامر مشتق شود. به عنوان مثالی مشابه، “Colorless green ideas sleep furiously” از چامسکی در سال ۱۹۵۷ را ببینید؛ برای یافتن مثال‌های زبانی طبیعی‌تر و مسائل گرامرهای رسمی در این زمینه، بخش‌های گرامر ساختار عبارت و قواعد ساختار عبارت را ببینید.
سلسه مراتب چامسکی شامل سطح‌های زیر است؛
توجه داشته باشید که مجموعه گرامرهای متناظر با زبان‌های بازگشتی عضو این سلسله مراتب نمی‌باشد؛ می‌تواند به درستی بین نوع صفر و نوع اول باشد.
هر زبان به طور منظم مستقل از متن است، هر زبان مستقل از متن (شامل رشته تهی نباشد) حساس به متن است، هر زبان حساس به متن بازگشتی است و هر زبان بازگشتی به صورت بازگشتی شمارش پذیر است. این شمول‌ها مناسب همه هستند، به این معنی که زبان‌های شمارش پذیر بازگشتی ای وجود دارند که حساس به متن نیستند، زبان‌های حساس به متن ای که مستقل از متن نیست و زبان‌های مستقل از متن که منظم نیست.
جدول زیر خلاصه هر یک از چهار نوع چامسکی از گرامرها، کلاسی که آن زبان تولید می‌کند، نوع اتوماتی که تشخیص می‌دهد و شکل قوانینی که دارد است.