موضوع مقاله: وراثت چامسکی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # وراثت چامسکی | مقدمه: وراثت چامسکی یا سلسله‌مراتب چامسکی یا سلسله‌مراتب چامسکی-شوتزنبرگر در زمینه‌های علوم کامپیوتر و زبان‌شناسی، به خصوص در زمینهٔ زبان‌های صوری، یک سلسله مراتب نگهدارندهٔ کلاس‌های دستور زبان صوری است. | ## بخش 1: وراثت چامسکی | در نام گذاری این سلسله مراتب، از اسم مارسل-پل شوتزنبرگر نیز به پاس نقش اساسی وی در توسعهٔ نظریهٔ زبان‌های رسمی (زبان صوری)، استفاده شده است. سلسله‌مراتب چامسکی در اصل امکان درک و بکارگیری مدل علوم کامپیوتر را فراهم می‌کند. این مدل به برنامه‌نویس‌ها اجازه می‌دهد که اهداف زبان‌شناسی مفهوم‌دار را به صورت سیستماتیک به انجام برسانند. دستور زبان‌های رسمی (صوری) مقالهٔ اصلی: دستور زبان صوری دستور زبانی رسمی از این نوع، از یک مجموعه‌ای متناهی از قواعد تولید تشکیل شده است (سمت چپ سمت راست) که هر سمت آن، خود شامل رشته‌ای از نمادهای زیر می‌باشد: مجموعه‌ای متناهی از نمادهای ناپایانه (که نشان‌دهندهٔ این است که هنوز برخی از قواعد تولید را می‌توان اعمال نمود) مجموعه‌ای متناهی از نمادهای پایانه (که نشان‌دهندهٔ این است که هیچ قاعدهٔ تولیدی را نمی‌توان اعمال نمود) یک نماد آغازین (یک نماد ناپایانهٔ متمایز) گرامر رسمی یک زبان رسمی را تعریف (یا تولید) می‌کند، که مجموعه‌ای (معمولاً متناهی) از رشته‌هایی با طول متناهی از نمادها هستند، که ممکن است با اعمال قواعد تولید به رشته‌ای دیگر از نمادها که از ابتدا فقط حاوی نماد آغازین بوده‌اند، ساخته شوند. یک قاعده می‌تواند با جایگزین کردن یک رخداد از نمادها در سمت چپ قاعده با رخدادی که در سمت راست ظاهر می‌شود، به رشته‌ای از نمادها اعمال شود. چنین گرامری زبان رسمی را تعریف می‌کند: همهٔ واژه‌هایی که تنها از نمادهای پایانه‌ای تشکیل شده باشند که با اشتقاقی از نماد آغازین، قابل دسترسی باشند. ناپایانهها معمولاً با حروف بزرگ، پایانه‌ها با حروف کوچک، و نماد آغازین با نمایش داده می‌شوند، مثلاً گرامری با پایانه‌های ، ناپایانه‌های ، قواعد تولید: ε (where ε is the empty string) و نماد آغازین ، زبان همهٔ واژه‌هایی با شکل را تعریف می‌کند (یعنی نسخه از و به دنبال آن کپی از ). مورد بعدی گرامر ساده‌تری است که زبان مشابهی را تعریف می‌کند: پایانه‌های ، ناپایانهٔ ، نماد آغازین ، قواعد تولید ε به عنوان مثالی دیگر، گرامری برای یک زیرمجموعهٔ سرگرمی از زبان انگلیسی، به صورت زیر داده شده است: پایانه‌های ، ناپایانه‌های ، قواعد تولید و نماد آغازین . | ## بخش 2: وراثت چامسکی | وراثت سلسه مراتب چامسکی شامل سطح‌های زیر است؛ گرامر نوع صفر (گرامر نامحدود) شامل تمام گرامرهای رسمی است. لازم است ذکر شود که با زبان بازگشتی که با تورینگ ماشین همیشه ایستا تشخیص داده می‌شود، متفاوت است. این گرامرها قوانینی به صورت با غیر پایانه و ، و رشته‌ای از پایانه‌ها یا\و غیر پایانه‌ها است. زبانهای توصیف شده با این گرامر، دقیقاً زبانهایی هستند که بعنوان آتاماتای خطی کران‌دار شناخته می‌شوند(ماشین تورینگ غیر قطعی ای که نوار آن به وسیله زمان ثابت طول ورودی آن کران دار است) گرامر نوع دوم(گرامر مستقل از متن) گرامر مستقل از متن را تولید می‌کند. اینها با قوانینی به فرم با غیر پایانه و رشته‌ای از پایانه‌ها یا\و غیر پایانه‌ها است. گرامر مستقل از متن - یا ترجیحاًٰ زیر مجموعه زبان مستقل از متن قطعی - پایه تئوری برای ساخت عبارتی بیشتر زبان‌های برنامه‌نویسی است، اگرچه گرامر آن‌ها شامل تبدیل نام به آدرس حساس به متن بر طبق اعلام‌ها و طرح نهایی است. اغلب یک زیر مجموعه از گرامرها برای راحت تجزیه کردن استفاده می‌شود، مانند یک تجزیه‌کنندهٔ ال‌ال. چنین گرامری قوانین محدود به یک غیر پایانه در سمت چپ و یک ترمینال در سمت راست دارد، احتمالاً به دنبال یک غیر پایانه (راست منظم). | ## بخش 3: وراثت چامسکی | متناوباً، سمت راست گرامر می‌تواند شامل یک پایانه باشد، احتمالاً قبل از یک غیر پایانه (چپ منظم)؛ این همان زبان را تولید می‌کند - اگر چه، اگر قوانین چپ و قوانین راست به طور منظم با هم ترکیب شوند، زبان نیازی ندارد منظم باشد. زبانهای توصیف شده با این گرامر، دقیقاً زبانهایی هستند که بعنوان ماشین حالات متناهی تصمیم‌گیری می‌شوند. علاوه بر این، این خانواده از زبان‌های رسمی را می‌توان به وسیله عبارت باقاعده به دست آورد. توجه داشته باشید که مجموعه گرامرهای متناظر با زبان‌های بازگشتی عضو این سلسله مراتب نمی‌باشد؛ می‌تواند به درستی بین نوع صفر و نوع اول باشد. هر زبان به طور منظم مستقل از متن است، هر زبان مستقل از متن (شامل رشته تهی نباشد) حساس به متن است، هر زبان حساس به متن بازگشتی است و هر زبان بازگشتی به صورت بازگشتی شمارش پذیر است. این شمول‌ها مناسب همه هستند، به این معنی که زبان‌های شمارش پذیر بازگشتی ای وجود دارند که حساس به متن نیستند، زبان‌های حساس به متن ای که مستقل از متن نیست و زبان‌های مستقل از متن که منظم نیست. | ## جمع‌بندی | خلاصه جدول زیر خلاصه هر یک از چهار نوع چامسکی از گرامرها، کلاسی که آن زبان تولید می‌کند، نوع اتوماتی که تشخیص می‌دهد و شکل قوانینی که دارد است.