وراثت چامسکی

مقالهٔ اصلی: دستور زبان صوری

دستور زبانی رسمی از این نوع، از یک مجموعه‌ای متناهی از قواعد تولید تشکیل شده است (سمت چپ ${\displaystyle \rightarrow \,}$ سمت راست) که هر سمت آن، خود شامل رشته‌ای از نمادهای زیر می‌باشد:

• مجموعه‌ای متناهی از نمادهای ناپایانه (که نشان‌دهندهٔ این است که هنوز برخی از قواعد تولید را می‌توان اعمال نمود)
• مجموعه‌ای متناهی از نمادهای پایانه (که نشان‌دهندهٔ این است که هیچ قاعدهٔ تولیدی را نمی‌توان اعمال نمود)
• یک نماد آغازین (یک نماد ناپایانهٔ متمایز)

گرامر رسمی یک زبان رسمی را تعریف (یا تولید) می‌کند، که مجموعه‌ای (معمولاً متناهی) از رشته‌هایی با طول متناهی از نمادها هستند، که ممکن است با اعمال قواعد تولید به رشته‌ای دیگر از نمادها که از ابتدا فقط حاوی نماد آغازین بوده‌اند، ساخته شوند. یک قاعده می‌تواند با جایگزین کردن یک رخداد از نمادها در سمت چپ قاعده با رخدادی که در سمت راست ظاهر می‌شود، به رشته‌ای از نمادها اعمال شود. رشته‌ای از کاربردهای قاعده را «اشتقاق» می‌خوانند. چنین گرامری زبان رسمی را تعریف می‌کند: همهٔ واژه‌هایی که تنها از نمادهای پایانه‌ای تشکیل شده باشند که با اشتقاقی از نماد آغازین، قابل دسترسی باشند. ناپایانهها معمولاً با حروف بزرگ، پایانه‌ها با حروف کوچک، و نماد آغازین با ${\displaystyle S}$ نمایش داده می‌شوند، مثلاً گرامری با پایانه‌های ${\displaystyle \{a,b\}}$ ، ناپایانه‌های ${\displaystyle \{S,A,B\}}$، قواعد تولید:

${\displaystyle S}$ ${\displaystyle \rightarrow \,}$ ${\displaystyle ABS}$

${\displaystyle S}$ ${\displaystyle \rightarrow \,}$ ε (where ε is the empty string)

${\displaystyle BA}$ ${\displaystyle \rightarrow \,}$ ${\displaystyle AB}$

${\displaystyle BS}$ ${\displaystyle \rightarrow \,}$ ${\displaystyle b}$

${\displaystyle Bb}$ ${\displaystyle \rightarrow \,}$ ${\displaystyle bb}$

${\displaystyle Ab}$ ${\displaystyle \rightarrow \,}$ ${\displaystyle ab}$

${\displaystyle Aa}$ ${\displaystyle \rightarrow \,}$ ${\displaystyle aa}$

و نماد آغازین ${\displaystyle S}$، زبان همهٔ واژه‌هایی با شکل ${\displaystyle a^{n}b^{n}}$ را تعریف می‌کند (یعنی ${\displaystyle n}$ نسخه از ${\displaystyle a}$ و به دنبال آن ${\displaystyle n}$ کپی از ${\displaystyle b}$). مورد بعدی گرامر ساده‌تری است که زبان مشابهی را تعریف می‌کند: پایانه‌های ${\displaystyle \{a,b\}}$، ناپایانهٔ ${\displaystyle \{S\}}$، نماد آغازین ${\displaystyle S}$ ، قواعد تولید

${\displaystyle S}$ ${\displaystyle \rightarrow \,}$ ${\displaystyle aSb}$

${\displaystyle S}$ ${\displaystyle \rightarrow \,}$ ε

به عنوان مثالی دیگر، گرامری برای یک زیرمجموعهٔ سرگرمی از زبان انگلیسی، به صورت زیر داده شده است: پایانه‌های ${\displaystyle \{generate,hate,great,green,ideas,linguists\}}$ ، ناپایانه‌های ${\displaystyle \{{\textit {SENTENCE}},{\textit {NOUNPHRASE}},{\textit {VERBPHRASE}},{\textit {NOUN}},{\textit {VERB}},{\textit {ADJ}}\}}$ ، قواعد تولید

${\displaystyle {\textit {SENTENCE}}}$ ${\displaystyle \rightarrow \,}$ ${\displaystyle {\textit {NOUNPHRASE}}\;{\textit {VERBPHRASE}}}$

${\displaystyle {\textit {NOUNPHRASE}}}$ ${\displaystyle \rightarrow \,}$ ${\displaystyle {\textit {ADJ}}\;{\textit {NOUNPHRASE}}}$

${\displaystyle {\textit {NOUNPHRASE}}}$ ${\displaystyle \rightarrow \,}$ ${\displaystyle {\textit {NOUN}}}$

${\displaystyle {\textit {VERBPHRASE}}}$ ${\displaystyle \rightarrow \,}$ ${\displaystyle {\textit {VERB}}\;{\textit {NOUNPHRASE}}}$

${\displaystyle {\textit {VERBPHRASE}}}$ ${\displaystyle \rightarrow \,}$ ${\displaystyle {\textit {VERB}}}$

${\displaystyle {\textit {NOUN}}}$ ${\displaystyle \rightarrow \,}$ ${\displaystyle {\textit {ideas}}}$

${\displaystyle {\textit {NOUN}}}$ ${\displaystyle \rightarrow \,}$ ${\displaystyle {\textit {linguists}}}$

${\displaystyle {\textit {VERB}}}$ ${\displaystyle \rightarrow \,}$ ${\displaystyle {\textit {generate}}}$

${\displaystyle {\textit {VERB}}}$ ${\displaystyle \rightarrow \,}$ ${\displaystyle {\textit {hate}}}$

${\displaystyle {\textit {ADJ}}}$ ${\displaystyle \rightarrow \,}$ ${\displaystyle {\textit {great}}}$

${\displaystyle {\textit {ADJ}}}$ ${\displaystyle \rightarrow \,}$ ${\displaystyle {\textit {green}}}$

و نماد آغازین ${\displaystyle {\textit {SENTENCE}}}$ . مثالی از اشتقاق این است:

SENTENCE ${\displaystyle \rightarrow }$ NOUNPHRASE VERBPHRASE ${\displaystyle \rightarrow }$ ADJ NOUNPHRASE VERBPHRASE ${\displaystyle \rightarrow }$ ADJ NOUN VERBPHRASE ${\displaystyle \rightarrow }$ ADJ NOUN VERB NOUNPHRASE ${\displaystyle \rightarrow }$ ADJ NOUN VERB ADJ NOUNPHRASE ${\displaystyle \rightarrow }$ ADJ NOUN VERB ADJ ADJ NOUNPHRASE ${\displaystyle \rightarrow }$ ADJ NOUN VERB ADJ ADJ NOUN ${\displaystyle \rightarrow }$ great NOUN VERB ADJ ADJ NOUN ${\displaystyle \rightarrow }$ great linguists VERB ADJ ADJ NOUN ${\displaystyle \rightarrow }$ great linguists generate ADJ ADJ NOUN ${\displaystyle \rightarrow }$ great linguists generate great ADJ NOUN ${\displaystyle \rightarrow }$ great linguists generate great green NOUN ${\displaystyle \rightarrow }$ great linguists generate great green ideas.

سایر رشته‌هایی که می‌توانند از این گرامر مشتق شوند "ideas hate greate linguists" و "ideas generate" هستند. این جملات بی‌معنی هستند، اما از لحاظ ساختاری صحیحند. جمله‌ای که از لحاظ ساختاری نادرست باشد، مثل "ideas ideas great hate"، نمی‌تواند از گرامر مشتق شود. به عنوان مثالی مشابه، “Colorless green ideas sleep furiously” از چامسکی در سال ۱۹۵۷ را ببینید؛ برای یافتن مثال‌های زبانی طبیعی‌تر و مسائل گرامرهای رسمی در این زمینه، بخش‌های گرامر ساختار عبارت و قواعد ساختار عبارت را ببینید.

سلسه مراتب چامسکی شامل سطح‌های زیر است؛

• گرامر نوع صفر (گرامر نامحدود) شامل تمام گرامرهای رسمی است. آن‌ها تمامی زبان‌هایی که به عنوان ماشین تورینگ شناخته می‌شوند را تولید می‌کنند. این زبان‌ها همچنین به عنوان زبان شمارش پذیر بازگشتی هم شناخته شده‌اند. لازم است ذکر شود که با زبان بازگشتی که با تورینگ ماشین همیشه ایستا تشخیص داده می‌شود، متفاوت است.
• گرامر نوع اول (گرامر حساس به متن) گرامر حساس به متن را تولید می‌کند. این گرامرها قوانینی به صورت ${\displaystyle \alpha A\beta \rightarrow \alpha \gamma \beta }$ با ${\displaystyle A}$ غیر پایانه و ${\displaystyle \alpha }$، ${\displaystyle \beta }$ و ${\displaystyle \gamma }$ رشته‌ای از پایانه‌ها یا\و غیر پایانه‌ها است. رشته‌های ${\displaystyle \alpha }$ و ${\displaystyle \beta }$ ممکن است تهی باشند ولی ${\displaystyle \gamma }$ نمی‌تواند تهی باشد. قانون ${\displaystyle S\rightarrow \epsilon }$ مجاز است اگر ${\displaystyle S}$ S در سمت راست هیچ‌کدام از قوانین ظاهر نشود. زبانهای توصیف شده با این گرامر، دقیقاً زبانهایی هستند که بعنوان آتاماتای خطی کران‌دار شناخته می‌شوند(ماشین تورینگ غیر قطعی ای که نوار آن به وسیله زمان ثابت طول ورودی آن کران دار است)
• گرامر نوع دوم(گرامر مستقل از متن) گرامر مستقل از متن را تولید می‌کند. اینها با قوانینی به فرم ${\displaystyle A\rightarrow \gamma }$ با ${\displaystyle A}$ غیر پایانه و ${\displaystyle \gamma }$ رشته‌ای از پایانه‌ها یا\و غیر پایانه‌ها است. این زبانها همان‌هایی هستند که به عنوان اتوماتون پشته‌ای غیرقطعی شناخته می‌شوند. گرامر مستقل از متن - یا ترجیحاًٰ زیر مجموعه زبان مستقل از متن قطعی - پایه تئوری برای ساخت عبارتی بیشتر زبان‌های برنامه‌نویسی است، اگرچه گرامر آن‌ها شامل تبدیل نام به آدرس حساس به متن بر طبق اعلام‌ها و طرح نهایی است. اغلب یک زیر مجموعه از گرامرها برای راحت تجزیه کردن استفاده می‌شود، مانند یک تجزیه‌کنندهٔ ال‌ال.
• گرامر نوع سوم (دستور زبان منظم) گرامر منظم را تولید می‌کند. چنین گرامری قوانین محدود به یک غیر پایانه در سمت چپ و یک ترمینال در سمت راست دارد، احتمالاً به دنبال یک غیر پایانه (راست منظم). متناوباً، سمت راست گرامر می‌تواند شامل یک پایانه باشد، احتمالاً قبل از یک غیر پایانه (چپ منظم)؛ این همان زبان را تولید می‌کند - اگر چه، اگر قوانین چپ و قوانین راست به طور منظم با هم ترکیب شوند، زبان نیازی ندارد منظم باشد. قانون ${\displaystyle S\rightarrow \epsilon }$ مجاز است اگر ${\displaystyle S}$ در سمت راست هیچ‌کدام از قوانین ظاهر نشود. زبانهای توصیف شده با این گرامر، دقیقاً زبانهایی هستند که بعنوان ماشین حالات متناهی تصمیم‌گیری می‌شوند. علاوه بر این، این خانواده از زبان‌های رسمی را می‌توان به وسیله عبارت باقاعده به دست آورد.

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

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

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

دستور زبان	زبان	خودکارسازی	قاعدهٔ تولید
نوع صفر	زبان شمارش‌پذیر بازگشتی	ماشین تورینگ	${\displaystyle \alpha \rightarrow \beta }$ (no restrictions)
نوع اول	حساس به متن	آتاماتای خطی کران‌دار	${\displaystyle \alpha A\beta \rightarrow \alpha \gamma \beta }$
نوع دوم	مستقل از متن	اتوماتون پشته‌ای	${\displaystyle A\rightarrow \gamma }$
نوع سوم	زبان منظم	ماشین حالات متناهی	${\displaystyle A\rightarrow a}$ و ${\displaystyle A\rightarrow aB}$

• «Chomsky.info». The Noam Chomsky website. بایگانی‌شده از اصلی در ۱۳ سپتامبر ۲۰۱۸. دریافت‌شده در تیرماه ۱۳۸۷. تاریخ وارد شده در |تاریخ بازدید= را بررسی کنید (کمک)
• «The Chomsky Hierarchy». National University of Ireland, Maynooth. بایگانی‌شده از اصلی در ۲۳ نوامبر ۲۰۰۷. دریافت‌شده در ۳ تیر ۱۳۸۷.
• https://web.archive.org/web/20080317131322/http://coral.lili.uni-bielefeld.de/Classes/Winter97/IntroCompPhon/compphon/node66.html
• http://www.staff.ncl.ac.uk/hermann.moisl/ell236/lecture5.htm
• Chomsky hierarchy. (2008, June 18). In Wikipedia, The Free Encyclopedia. Retrieved 18:30, July 3, 2008, from http://en.wikipedia.org/w/index.php?title=Chomsky_hierarchy&oldid=220223801
• Chomsky, Noam (1959). "On certain formal properties of grammars" (PDF). Information and Control. 2 (2): 137–167. doi:10.1016/S0019-9958(59)90362-6. Archived from the original (PDF) on 23 September 2015. Retrieved 27 June 2015.
• Chomsky, Noam; Schützenberger, Marcel P. (1963). "The algebraic theory of context free languages". In Braffort, P.; Hirschberg, D. Computer Programming and Formal Languages. Amsterdam: North Holland. pp. 118–161.
• Davis, Martin D.; Sigal, Ron; Weyuker, Elaine J. (1994). Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science (2nd ed.). Boston: Academic Press, Harcourt, Brace. p. 327. ISBN 0-12-206382-1.

• http://www.dlsi.ua.es/~mlf/nnafmc/pbook/node46.html
• http://dingo.sbs.arizona.edu/~langendoen/LING501/LING501chomskyhierarchy.htm
• https://web.archive.org/web/20080329070526/http://www.augustana.ab.ca/~mohrj/courses/common/csc370/lecture_notes/chomsky.html