نظریه زبان‌ها: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
اصلاح اشتباهات مقاله |
گسترش بخش نخست |
||
خط ۱:
در [[منطق]]، [[ریاضیات]]، [[علوم رایانه|علوم کامپیوتر]] و [[زبان‌شناسی]]، '''نظریهٔ زبان‌ها''' به مطالعهٔ زبان‌هایی صوری و دسته‌بندی آنها می‌پردازد. در نظریهٔ زبان‌ها تنها جنبه‌های [[نحو|نحوی]] زبان‌ها (یعنی الگوهای ساختاری درونی آنها) [[مدل ریاضی|تجرید و انتزاع می‌شود]] و به معنای جملات و ... اهمیتی نمی‌دهیم (مثلاً جملهٔ «رنگ آسمان قرمز است» ممکن است در یک زبان صوری جملهٔ مورد قبولی باشد).
در [[منطق]]، [[ریاضیات]]، [[علوم رایانه|علوم کامپیوتر]] و [[زبان‌شناسی]]، یک '''زبان صوری''' {{به انگلیسی|formal language}} شامل [[الفبا (نظریه زبان‌ها)#%D8%B1%D8%B4%D8%AA%D9%87|کلماتی]] است متشکل از [[الفبا (نظریه زبان‌ها)|حروف یک الفبا]] که بر اساس قوانینی به صورت خوش‌ساخت شکل بگیرند.<ref name=":1">{{یادکرد کتاب|عنوان=An Introduction to Formal Languages and Automata (Sixth Edition)|کوشش=Peter Linz|شناسه=978-1-284-07724-7}}</ref><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> مفهوم [[دستور زبان صوری|گرامر صوری]] شباهت بیشتری به [[زبان طبیعی|تصور انسانی از یک زبان]] دارد. زبانی که با قواعد [[نحو|نحوی]] محدود شده باشد.
سطر ۱۴ ⟵ ۱۸:
گاهی برای توصیف زبان‌ها از [[دستور زبان صوری]] استفاده می‌شود و در این مواقع یک زبان را مجهز به یک گرامر فرض می‌کنیم: <math>\mathcal{L} = (L, G)</math>
=== اعمال روی زبان‌ها ===
ماهیت زبان‌ها [[مجموعه (ریاضیات)|مجموعه]] است؛ در نتیجه [[جبر مجموعه‌ها|اعمال مجموعه‌ها]] (تفاضل، [[اجتماع (نظریه مجموعه‌ها)|اجتماع]]، [[اشتراک (نظریه مجموعه‌ها)|اشتراک]] و [[تفاضل متقارن]]) روی آنها نیز تعریف می‌شود:<ref name=":1" />
سطر ۳۱ ⟵ ۳۵:
برای تولید یا توصیف یک زبان از [[دستور زبان صوری|گرامر صوری]]، [[نظریه اتوماتا|اتوماتان]]، [[عبارت باقاعده|عبارات باقاعده]] {{به انگلیسی|regex}} یا [[مدل محاسباتی|مدل‌های محاسباتی]] استفاده می‌شود.
[[مسئله تصمیم|مسئلهٔ تصمیم]] معادل [[عنصر (ریاضیات)|عضویت]] در یک زبان صوری است. مجموعهٔ همهٔ رشته‌هایی که یک اتوماتا می‌پذیرد (یا یک گرامر تولید می‌کند یا با یک عبارت باقاعده تطابق دارند) یک زبان است. همچنین پذیرش یک رشته توسط یک ماشین معادل عضویت آن در زبان مذکور است. بنابراین نظریه زبان‌ها بسیار با [[نظریه ماشین ها|نظریهٔ ماشین‌ها]] مرتبط است و همچنین یک حوزه کاربردی اصلی در [[نظریه رایانش‌پذیری]] و [[نظریه پیچیدگی محاسباتی|نظریهٔ پیچیدگی محاسباتی]] است.<ref name=":2" />
زبان‌های صوری را می‌توان به کمک [[وراثت چامسکی]] بر اساس قدرت مولد ([[دستور زبان صوری|گرامر]]) آنها و یا پیچیدگی [[نظریه اتوماتا|اتوماتای]] تصمیم آنها طبقه بندی کرد.
== منابع ==
| |||