نظریه زبانها: تفاوت میان نسخهها
جز Aliheidary1381 صفحهٔ زبان صوری را به نظریه زبانها منتقل کرد: در منابع فارسی به اصطلاح نظریه زبانها اشارهٔ بیشتری شده و نسبت به ترجمهٔ تحت الفظی «زبان صوری» عنوان مناسبتری است. |
بدون خلاصۀ ویرایش |
||
خط ۱: | خط ۱: | ||
در [[منطق]]، [[ریاضیات]]، [[علوم رایانه|علوم کامپیوتر]] و [[زبانشناسی]]، '''نظریهٔ زبانها''' به مطالعهٔ |
در [[منطق]]، [[ریاضیات]]، [[علوم رایانه|علوم کامپیوتر]] و [[زبانشناسی]]، '''نظریهٔ زبانها''' به مطالعهٔ زبانهای صوری و دستهبندی آنها میپردازد. در نظریهٔ زبانها تنها جنبههای [[نحو|نحوی]] زبانها (یعنی الگوهای ساختاری درونی آنها) [[مدل ریاضی|تجرید و انتزاع میشود]] و به معنای جملات و ... اهمیتی نمیدهیم (مثلاً جملهٔ «رنگ آسمان قرمز است» ممکن است در یک زبان صوری جملهٔ مورد قبولی باشد). |
||
نظریهٔ زبانها به عنوان راهی برای درک قوانین نحوی [[زبان طبیعی|زبانهای طبیعی]] از [[زبان شناسی]] سرچشمه گرفت و [[نوام چامسکی]] در پیشرفت آن نقش مؤثری داشت. در [[علوم رایانه|علوم کامپیوتر]]، زبانهای صوری به عنوان مبنایی برای تعریف دستور [[زبان برنامهنویسی|زبانهای برنامهنویسی]] استفاده میشوند. در [[نظریه پیچیدگی محاسباتی|نظریهٔ پیچیدگی محاسباتی]]، [[مسئله تصمیم|مسائل تصمیم]] معمولاً به عنوان زبانهای صوری تعریف میشوند و [[کلاس پیچیدگی|کلاسهای پیچیدگی]] به عنوان مجموعهای از زبانهای صوری تعریف میشوند که میتوانند توسط ماشینهای [[تجزیهکننده|تجزیهگر]] تجزیه شوند. در [[منطق]]، فرمالیسم ریاضی و [[بنیانهای ریاضیات|مبانی ریاضی]]، از زبانهای صوری برای تعریف دقیق نحو [[دستگاه صوری|دستگاههای صوری]] همچون [[نظریه مجموعهها|نظریهٔ مجموعهها]] استفاده میشود. |
نظریهٔ زبانها به عنوان راهی برای درک قوانین نحوی [[زبان طبیعی|زبانهای طبیعی]] از [[زبان شناسی]] سرچشمه گرفت و [[نوام چامسکی]] در پیشرفت آن نقش مؤثری داشت. در [[علوم رایانه|علوم کامپیوتر]]، زبانهای صوری به عنوان مبنایی برای تعریف دستور [[زبان برنامهنویسی|زبانهای برنامهنویسی]] استفاده میشوند. در [[نظریه پیچیدگی محاسباتی|نظریهٔ پیچیدگی محاسباتی]]، [[مسئله تصمیم|مسائل تصمیم]] معمولاً به عنوان زبانهای صوری تعریف میشوند و [[کلاس پیچیدگی|کلاسهای پیچیدگی]] به عنوان مجموعهای از زبانهای صوری تعریف میشوند که میتوانند توسط ماشینهای [[تجزیهکننده|تجزیهگر]] تجزیه شوند. در [[منطق]]، فرمالیسم ریاضی و [[بنیانهای ریاضیات|مبانی ریاضی]]، از زبانهای صوری برای تعریف دقیق نحو [[دستگاه صوری|دستگاههای صوری]] همچون [[نظریه مجموعهها|نظریهٔ مجموعهها]] استفاده میشود.<ref name=":1">{{یادکرد کتاب|عنوان=An Introduction to Formal Languages and Automata (Sixth Edition)|کوشش=Peter Linz|شناسه=978-1-284-07724-7}}</ref> |
||
یک '''زبان صوری''' {{به انگلیسی|formal language}} شامل [[الفبا (نظریه زبانها)#%D8%B1%D8%B4%D8%AA%D9%87|کلماتی]] است متشکل از [[الفبا (نظریه زبانها)|حروف یک الفبا]] که بر اساس قوانینی به صورت خوشساخت شکل بگیرند. |
یک '''زبان صوری''' {{به انگلیسی|formal language}} شامل [[الفبا (نظریه زبانها)#%D8%B1%D8%B4%D8%AA%D9%87|کلماتی]] است متشکل از [[الفبا (نظریه زبانها)|حروف یک الفبا]] که بر اساس قوانینی به صورت خوشساخت شکل بگیرند.<ref name=":2">{{یادکرد کتاب|عنوان=Introduction to Automata Theory, Languages, and Computation (Third Edition)|شناسه=0-321-45536-3|کوشش=John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman}}</ref> |
||
در علوم کامپیوتر و ریاضیات که معمولاً با [[زبان طبیعی|زبانهای طبیعی]] سروکار ندارند، صفت «صوری» [[حذف به قرینه|حذف]] می شود.<ref name=":0">{{یادکرد کتاب|عنوان=Introduction to the Theory of Computation (Third Edition)|کوشش=Michael Sipser|شناسه=978-1-133-18781-3}}</ref> مفهوم [[دستور زبان صوری|گرامر صوری]] شباهت بیشتری به [[زبان طبیعی|تصور انسانی از یک زبان]] دارد. زبانی که با قواعد [[نحو|نحوی]] محدود شده باشد. |
در علوم کامپیوتر و ریاضیات که معمولاً با [[زبان طبیعی|زبانهای طبیعی]] سروکار ندارند، صفت «صوری» [[حذف به قرینه|حذف]] می شود.<ref name=":0">{{یادکرد کتاب|عنوان=Introduction to the Theory of Computation (Third Edition)|کوشش=Michael Sipser|شناسه=978-1-133-18781-3}}</ref> مفهوم [[دستور زبان صوری|گرامر صوری]] شباهت بیشتری به [[زبان طبیعی|تصور انسانی از یک زبان]] دارد. زبانی که با قواعد [[نحو|نحوی]] محدود شده باشد. |
||
خط ۱۱: | خط ۱۱: | ||
[[الفبا (نظریه زبانها)|'''الفبای''' صوری]] مجموعهٔ حروفی (مثل الف، ب، پ و ...) به نام '''نماد''' است که با قرارگیری آنها در کنار هم (الحاقشان) کلماتی به نام '''رشته''' پدید میآیند. هر کلمهٔ صوری از به هم پیوستن حروف این الفبا به دست میآید. مثلاً کلمهٔ «آب» (با حروف آ + ب) به زبان [[زبان فارسی|فارسی]] تعلق دارد ولی در [[زبان عربی|عربی]] معنا ندارد (با این وجود [[الفبای فارسی|الفبای آنها]] یکسان است). گاهی کلماتی که به یک زبان صوری خاص تعلق دارند ''[[فرمول خوش فرم|جمله یا فرمولهای خوشفرم]]'' نامیده می شوند.<ref name=":1" /> |
[[الفبا (نظریه زبانها)|'''الفبای''' صوری]] مجموعهٔ حروفی (مثل الف، ب، پ و ...) به نام '''نماد''' است که با قرارگیری آنها در کنار هم (الحاقشان) کلماتی به نام '''رشته''' پدید میآیند. هر کلمهٔ صوری از به هم پیوستن حروف این الفبا به دست میآید. مثلاً کلمهٔ «آب» (با حروف آ + ب) به زبان [[زبان فارسی|فارسی]] تعلق دارد ولی در [[زبان عربی|عربی]] معنا ندارد (با این وجود [[الفبای فارسی|الفبای آنها]] یکسان است). گاهی کلماتی که به یک زبان صوری خاص تعلق دارند ''[[فرمول خوش فرم|جمله یا فرمولهای خوشفرم]]'' نامیده می شوند.<ref name=":1" /> |
||
== |
== زبان صوری == |
||
هر [[مجموعه (ریاضیات)|مجموعهای]] از [[الفبا (نظریه زبانها)#%D8%B1%D8%B4%D8%AA%D9%87|رشتهها (یا کلمات)]] از یک [[الفبا (نظریه زبانها)|الفبای]] خاص <math>\Sigma</math> را یک '''زبان صوری''' <math>L</math> در <math>\Sigma</math> (یا بر روی <math>\Sigma</math>) مینامیم. به عبارتی دیگر <math>L \subseteq \Sigma^*</math> است.<ref name=":1" /> |
هر [[مجموعه (ریاضیات)|مجموعهای]] از [[الفبا (نظریه زبانها)#%D8%B1%D8%B4%D8%AA%D9%87|رشتهها (یا کلمات)]] از یک [[الفبا (نظریه زبانها)|الفبای]] خاص <math>\Sigma</math> را یک '''زبان صوری''' <math>L</math> در <math>\Sigma</math> (یا بر روی <math>\Sigma</math>) مینامیم. به عبارتی دیگر <math>L \subseteq \Sigma^*</math> است.<ref name=":1" /> |
||
خط ۳۳: | خط ۳۳: | ||
== توصیف زبانها == |
== توصیف زبانها == |
||
برای تولید یا توصیف یک زبان از [[دستور زبان صوری|گرامر صوری]]، [[نظریه اتوماتا|اتوماتان]]، [[عبارت باقاعده|عبارات باقاعده]] {{به انگلیسی|regex}} یا [[مدل محاسباتی|مدلهای محاسباتی]] استفاده میشود. |
برای تولید یا توصیف یک زبان از [[دستور زبان صوری|گرامر صوری]]، [[نظریه اتوماتا|اتوماتان]]، [[عبارت باقاعده|عبارات باقاعده]] {{به انگلیسی|regex}} یا [[مدل محاسباتی|مدلهای محاسباتی]] استفاده میشود.<ref name=":2" /> |
||
[[مسئله تصمیم|مسئلهٔ تصمیم]] معادل [[عنصر (ریاضیات)|عضویت]] در یک زبان صوری است. مجموعهٔ همهٔ رشتههایی که یک اتوماتا میپذیرد (یا یک گرامر تولید میکند یا با یک عبارت باقاعده تطابق دارند) یک زبان است. همچنین پذیرش یک رشته توسط یک ماشین معادل عضویت آن در زبان مذکور است. بنابراین نظریه زبانها بسیار با [[نظریه ماشین ها|نظریهٔ ماشینها]] مرتبط است و همچنین یک حوزه کاربردی اصلی در [[نظریه رایانشپذیری]] و [[نظریه پیچیدگی محاسباتی|نظریهٔ پیچیدگی محاسباتی]] است.<ref name=":2" /> |
[[مسئله تصمیم|مسئلهٔ تصمیم]] معادل [[عنصر (ریاضیات)|عضویت]] در یک زبان صوری است. مجموعهٔ همهٔ رشتههایی که یک اتوماتا میپذیرد (یا یک گرامر تولید میکند یا با یک عبارت باقاعده تطابق دارند) یک زبان است. همچنین پذیرش یک رشته توسط یک ماشین معادل عضویت آن در زبان مذکور است. بنابراین نظریه زبانها بسیار با [[نظریه ماشین ها|نظریهٔ ماشینها]] مرتبط است و همچنین یک حوزه کاربردی اصلی در [[نظریه رایانشپذیری]] و [[نظریه پیچیدگی محاسباتی|نظریهٔ پیچیدگی محاسباتی]] است.<ref name=":2" /> |
نسخهٔ ۲۶ مارس ۲۰۲۲، ساعت ۱۸:۲۴
در منطق، ریاضیات، علوم کامپیوتر و زبانشناسی، نظریهٔ زبانها به مطالعهٔ زبانهای صوری و دستهبندی آنها میپردازد. در نظریهٔ زبانها تنها جنبههای نحوی زبانها (یعنی الگوهای ساختاری درونی آنها) تجرید و انتزاع میشود و به معنای جملات و ... اهمیتی نمیدهیم (مثلاً جملهٔ «رنگ آسمان قرمز است» ممکن است در یک زبان صوری جملهٔ مورد قبولی باشد).
نظریهٔ زبانها به عنوان راهی برای درک قوانین نحوی زبانهای طبیعی از زبان شناسی سرچشمه گرفت و نوام چامسکی در پیشرفت آن نقش مؤثری داشت. در علوم کامپیوتر، زبانهای صوری به عنوان مبنایی برای تعریف دستور زبانهای برنامهنویسی استفاده میشوند. در نظریهٔ پیچیدگی محاسباتی، مسائل تصمیم معمولاً به عنوان زبانهای صوری تعریف میشوند و کلاسهای پیچیدگی به عنوان مجموعهای از زبانهای صوری تعریف میشوند که میتوانند توسط ماشینهای تجزیهگر تجزیه شوند. در منطق، فرمالیسم ریاضی و مبانی ریاضی، از زبانهای صوری برای تعریف دقیق نحو دستگاههای صوری همچون نظریهٔ مجموعهها استفاده میشود.[۱]
یک زبان صوری (به انگلیسی: formal language) شامل کلماتی است متشکل از حروف یک الفبا که بر اساس قوانینی به صورت خوشساخت شکل بگیرند.[۲]
در علوم کامپیوتر و ریاضیات که معمولاً با زبانهای طبیعی سروکار ندارند، صفت «صوری» حذف می شود.[۳] مفهوم گرامر صوری شباهت بیشتری به تصور انسانی از یک زبان دارد. زبانی که با قواعد نحوی محدود شده باشد.
تعاریف پایه
الفبای صوری مجموعهٔ حروفی (مثل الف، ب، پ و ...) به نام نماد است که با قرارگیری آنها در کنار هم (الحاقشان) کلماتی به نام رشته پدید میآیند. هر کلمهٔ صوری از به هم پیوستن حروف این الفبا به دست میآید. مثلاً کلمهٔ «آب» (با حروف آ + ب) به زبان فارسی تعلق دارد ولی در عربی معنا ندارد (با این وجود الفبای آنها یکسان است). گاهی کلماتی که به یک زبان صوری خاص تعلق دارند جمله یا فرمولهای خوشفرم نامیده می شوند.[۱]
زبان صوری
هر مجموعهای از رشتهها (یا کلمات) از یک الفبای خاص را یک زبان صوری در (یا بر روی ) مینامیم. به عبارتی دیگر است.[۱]
با این تعریف مجموعهٔ تهی نیز یک زبان (زبان تهی بر روی هر دلخواه) محسوب میشود. در یک زبان لزومی ندارد که از همهٔ حروف الفبا استفاده شود.[۲]
گاهی برای توصیف زبانها از دستور زبان صوری استفاده میشود و در این مواقع یک زبان را مجهز به یک گرامر فرض میکنیم:
اعمال روی زبانها
ماهیت زبانها مجموعه است؛ در نتیجه اعمال مجموعهها (تفاضل، اجتماع، اشتراک و تفاضل متقارن) روی آنها نیز تعریف میشود:[۱]
- کاردینالیتی (تعداد اعضای) اکثر زبانها بینهایت است.
- متمم یک زبان روی الفبای برابر است با .
همچنین اعمال روی رشتهها و الفبا نیز روی زبانها قابل تعمیم است:[۱]
- الحاق مجموعهٔ تمام رشتههای حاصل از الحاق اعضای این دو است:
- توان با بار الحاق در خودش به دست میآید: همچنین تعریف میکنیم. توجه کنید که .[۲]
- معکوس مجموعهٔ معکوس تمام رشتههای زبان مذکور است:
- بستار کلین به صورت تعریف میکنیم.
- همچنین بستار مثبت را به این شکل تعریف میکنیم:
توصیف زبانها
برای تولید یا توصیف یک زبان از گرامر صوری، اتوماتان، عبارات باقاعده (به انگلیسی: regex) یا مدلهای محاسباتی استفاده میشود.[۲]
مسئلهٔ تصمیم معادل عضویت در یک زبان صوری است. مجموعهٔ همهٔ رشتههایی که یک اتوماتا میپذیرد (یا یک گرامر تولید میکند یا با یک عبارت باقاعده تطابق دارند) یک زبان است. همچنین پذیرش یک رشته توسط یک ماشین معادل عضویت آن در زبان مذکور است. بنابراین نظریه زبانها بسیار با نظریهٔ ماشینها مرتبط است و همچنین یک حوزه کاربردی اصلی در نظریه رایانشپذیری و نظریهٔ پیچیدگی محاسباتی است.[۲]
زبانهای صوری را میتوان به کمک وراثت چامسکی بر اساس قدرت مولد (گرامر) آنها و یا پیچیدگی اتوماتای تصمیم آنها طبقه بندی کرد.
منابع
- ↑ ۱٫۰ ۱٫۱ ۱٫۲ ۱٫۳ ۱٫۴ An Introduction to Formal Languages and Automata (Sixth Edition). به کوشش Peter Linz.
- ↑ ۲٫۰ ۲٫۱ ۲٫۲ ۲٫۳ ۲٫۴ Introduction to Automata Theory, Languages, and Computation (Third Edition). به کوشش John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman.
- ↑ Introduction to the Theory of Computation (Third Edition). به کوشش Michael Sipser.
- Sudkamp, T. A. , An Introduction to the Theory of Computer Science, Languages and Machines, 3rd ed. , Pearson Education, Inc. , 2006. ISBN 0-321-32221-5 [۱]