نظریه زبان‌ها: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
جز 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|کلماتی]] است متشکل از [[الفبا (نظریه زبان‌ها)|حروف یک الفبا]] که بر اساس قوانینی به صورت خوش‌ساخت شکل بگیرند.
در علوم کامپیوتر و ریاضیات که معمولاً با [[زبان طبیعی|زبان‌های طبیعی]] سروکار ندارند، صفت «صوری» [[حذف به قرینه|حذف]] می شود.<ref name=":0">{{یادکرد کتاب|عنوان=Introduction to the Theory of Computation (Third Edition)|کوشش=Michael Sipser|شناسه=978-1-133-18781-3}}</ref> مفهوم [[دستور زبان صوری|گرامر صوری]] شباهت بیشتری به [[زبان طبیعی|تصور انسانی از یک زبان]] دارد. زبانی که با قواعد [[نحو|نحوی]] محدود شده باشد.
خط ۱۱:
[[الفبا (نظریه زبان‌ها)|'''الفبای''' صوری]] مجموعهٔ حروفی (مثل الف، ب، پ و ...) به نام '''نماد''' است که با قرارگیری آنها در کنار هم (الحاقشان) کلماتی به نام '''رشته''' پدید می‌آیند. هر کلمهٔ صوری از به هم پیوستن حروف این الفبا به دست می‌آید. مثلاً کلمهٔ «آب» (با حروف آ + ب) به زبان [[زبان فارسی|فارسی]] تعلق دارد ولی در [[زبان عربی|عربی]] معنا ندارد (با این وجود [[الفبای فارسی|الفبای آنها]] یکسان است). گاهی کلماتی که به یک زبان صوری خاص تعلق دارند ''[[فرمول خوش فرم|جمله یا فرمول‌های خوش‌فرم]]'' نامیده می شوند.<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}} یا [[مدل محاسباتی|مدل‌های محاسباتی]] استفاده می‌شود.<ref name=":2" />
[[مسئله تصمیم|مسئلهٔ تصمیم]] معادل [[عنصر (ریاضیات)|عضویت]] در یک زبان صوری است. مجموعهٔ همهٔ رشته‌هایی که یک اتوماتا می‌پذیرد (یا یک گرامر تولید می‌کند یا با یک عبارت باقاعده تطابق دارند) یک زبان است. همچنین پذیرش یک رشته توسط یک ماشین معادل عضویت آن در زبان مذکور است. بنابراین نظریه زبان‌ها بسیار با [[نظریه ماشین ها|نظریهٔ ماشین‌ها]] مرتبط است و همچنین یک حوزه کاربردی اصلی در [[نظریه رایانش‌پذیری]] و [[نظریه پیچیدگی محاسباتی|نظریهٔ پیچیدگی محاسباتی]] است.<ref name=":2" />
| |||