وراثت چامسکی

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

در زمینه‎ های علوم کامپیوتر و زبان‎شناسی، به خصوص در زمینه‎ ی زبان‎های رسمی، سلسله‎ مراتب چامسکی (به انگلیسی: وراثت چامسکی) (گاهی اوقات به آن سلسله‎ مراتب چامسکی-شوتزنبرگر می‎گویند) یک سلسله ‎مراتب نگهدارنده‎ ی کلاس‎های گرامرهای رسمی است. سلسله‎مراتب گرامرها توسط نوآم چامسکی (به انگلیسی: نوآم چامسکی) در سال ۱۹۵۶ توصیف شده است. در نام‎ گذاری این سلسله‎ مراتب، از اسم مارسل-پل شوتزنبرگر (به انگلیسی: Marcel-Paul Schützenberger) نیز به پاس نقش اساسی وی در توسعه‎ی نظریه‎ی زبان‎های رسمی(زبان صوری)، استفاده شده است. سلسله‎مراتب چامسکی در اصل امکان درک و بکارگیری مدل علوم کامپیوتر را فراهم می‎کند. این مدل به برنامه ‎نویس ‎ها اجازه می‎دهد که اهداف زبان‎ شناسی مفهوم‎ دار را به صورت سیستماتیک به انجام برسانند.


دستور زبان های رسمی[ویرایش]

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

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

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

S \rightarrow \, ABS
S \rightarrow \, ε (where ε is the empty string)
BA \rightarrow \, AB
BS \rightarrow \, b
Bb \rightarrow \, bb
Ab \rightarrow \, ab
Aa \rightarrow \, aa

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

S \rightarrow \, aSb
S \rightarrow \, ε

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

\textit{SENTENCE} \rightarrow \, \textit{NOUNPHRASE} \; \textit{VERBPHRASE}
\textit{NOUNPHRASE} \rightarrow \, \textit{ADJ} \; \textit{NOUNPHRASE}
\textit{NOUNPHRASE} \rightarrow \, \textit{NOUN}
\textit{VERBPHRASE} \rightarrow \, \textit{VERB} \;  \textit{NOUNPHRASE}
\textit{VERBPHRASE} \rightarrow \, \textit{VERB}
\textit{NOUN} \rightarrow \, \textit{ideas}
\textit{NOUN} \rightarrow \, \textit{linguists}
\textit{VERB} \rightarrow \, \textit{generate}
\textit{VERB} \rightarrow \, \textit{hate}
\textit{ADJ} \rightarrow \, \textit{great}
\textit{ADJ} \rightarrow \, \textit{green}

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

SENTENCE \rightarrow NOUNPHRASE VERBPHRASE \rightarrow ADJ NOUNPHRASE VERBPHRASE \rightarrow ADJ NOUN VERBPHRASE \rightarrow ADJ NOUN VERB NOUNPHRASE \rightarrow ADJ NOUN VERB ADJ NOUNPHRASE \rightarrow ADJ NOUN VERB ADJ ADJ NOUNPHRASE \rightarrow ADJ NOUN VERB ADJ ADJ NOUN \rightarrow great NOUN VERB ADJ ADJ NOUN \rightarrow great linguists VERB ADJ ADJ NOUN \rightarrow great linguists generate ADJ ADJ NOUN \rightarrow great linguists generate great ADJ NOUN \rightarrow great linguists generate great green NOUN \rightarrow great linguists generate great green ideas.

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

وراثت[ویرایش]

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

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

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

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

خلاصه‌[ویرایش]

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


Grammar Languages Automaton Production rules (constraints)
نوع صفر Recursively enumerable ماشین تورینگماشین تورینگ \alpha \rightarrow \beta (no restrictions)
نوع اول Context-sensitiveحساس به متن Linear-bounded non-deterministic Turing machine \alpha A \beta \rightarrow \alpha \gamma \beta
نوع دوم Context-freeمستقل از متن Non-deterministic pushdown automatonاتوماتون پشته‌ای A \rightarrow \gamma
نوع سوم Regularمنظم ماشین حالات متناهیماشین حالات متناهی A \rightarrow a
و
A \rightarrow aB

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

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