نمایش مبدأ برای نظریه زبان‌ها

{{اصلاح ترجمه}}
== زبان فرمالیسم |زبان قراردادی |زبان صوری ==

در [[منطق]]، [[ریاضیات]]، [[علوم رایانه|علوم کامپیوتر]] و [[زبان‌شناسی]]، '''نظریهٔ زبان‌ها''' به مطالعهٔ زبان‌های قراردادی و دسته‌بندی آنها می‌پردازد. در نظریهٔ زبان‌ها تنها جنبه‌های [[نحو|نحوی]] زبان‌ها (یعنی الگوهای ساختاری درونی آنها) [[مدل ریاضی|تجرید و انتزاع می‌شود]] و به معنای جملات و ... اهمیتی نمی‌دهیم (مثلاً جملهٔ «رنگ آسمان قرمز است» ممکن است در یک زبان قراردادی جملهٔ مورد قبولی باشد).

نظریهٔ زبان‌ها به عنوان راهی برای درک قوانین نحوی [[زبان طبیعی|زبان‌های طبیعی]] از [[زبان‌شناسی]] سرچشمه گرفت و [[نوام چامسکی]] در پیشرفت آن نقش مؤثری داشت. در [[علوم رایانه|علوم کامپیوتر]]، زبان‌های قراردادی به عنوان مبنایی برای تعریف دستور [[زبان برنامه‌نویسی|زبان‌های برنامه‌نویسی]] استفاده می‌شوند. در [[نظریه پیچیدگی محاسباتی|نظریهٔ پیچیدگی محاسباتی]]، [[مسئله تصمیم|مسائل تصمیم]] معمولاً به عنوان زبان‌های قراردادی تعریف می‌شوند و [[کلاس پیچیدگی|کلاس‌های پیچیدگی]] به عنوان مجموعه‌ای از زبان‌های قراردادی تعریف می‌شوند که می‌توانند توسط ماشین‌های [[تجزیه‌کننده|تجزیه‌گر]] تجزیه شوند. در [[منطق]]، فرمالیسم ریاضی و [[بنیان‌های ریاضیات|مبانی ریاضی]]، از زبان‌های قراردادی برای تعریف دقیق نحو [[ماشین مجازی|ماشین های مجازی]] همچون [[نظریه مجموعه‌ها|نظریهٔ مجموعه‌ها]] استفاده می‌شود.<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=":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=":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" />

با این تعریف [[مجموعه تهی|مجموعهٔ تهی]] نیز یک زبان (زبان تهی بر روی هر <math>\Sigma</math> دلخواه) محسوب می‌شود. در یک زبان لزومی ندارد که از همهٔ حروف الفبا استفاده شود.<ref name=":2" />

گاهی برای توصیف زبان‌ها از [[دستور زبان قراردادی]] استفاده می‌شود و در این مواقع یک زبان را مجهز به یک گرامر فرض می‌کنیم: <math>\mathcal{L} = (L, G)</math>

=== اعمال روی زبان‌ها ===
ماهیت زبان‌ها [[مجموعه (ریاضیات)|مجموعه]] است؛ در نتیجه [[جبر مجموعه‌ها|اعمال مجموعه‌ها]] (تفاضل، [[اجتماع (نظریه مجموعه‌ها)|اجتماع]]، [[اشتراک (نظریه مجموعه‌ها)|اشتراک]] و [[تفاضل متقارن]]) روی آنها نیز تعریف می‌شود:<ref name=":1" />

* [[کاردینالیتی]] (تعداد اعضای) اکثر زبان‌ها [[بی‌نهایت]] است.
* [[متمم (نظریه مجموعه‌ها)|'''متمم''']] یک زبان <math>L</math> روی [[الفبا (نظریه زبان‌ها)|الفبای]] <math>\Sigma</math> برابر است با <math>\overline{L} = \Sigma^* \backslash L</math>.

همچنین [[الفبا (نظریه زبان‌ها)#%D8%A7%D8%B9%D9%85%D8%A7%D9%84%20%D8%B1%D9%88%DB%8C%20%D8%B1%D8%B4%D8%AA%D9%87%E2%80%8C%D9%87%D8%A7|اعمال روی رشته‌ها]] و [[الفبا (نظریه زبان‌ها)#توان الفبا|الفبا]] نیز روی زبان‌ها قابل تعمیم است:<ref name=":1" />

* ''[[الفبا (نظریه زبان‌ها)#%D8%A7%D9%84%D8%AD%D8%A7%D9%82%20%D8%B1%D8%B4%D8%AA%D9%87%E2%80%8C%D9%87%D8%A7|الحاق]]'' <math>L_1 \circ L_2</math><ref name=":0" /> مجموعهٔ تمام رشته‌های حاصل از الحاق اعضای این دو است: <math>L_1 \cdot L_2 = L_1 L_2 = \{ vw : v \in L_1 \and w \in L_2 \}</math>
* [[الفبا (نظریه زبان‌ها)#%D8%AA%D9%88%D8%A7%D9%86%20%D8%B1%D8%B4%D8%AA%D9%87|توان]] <math>L^n</math> با <math>n</math> بار الحاق <math>L</math> در خودش به دست می‌آید: <math>L^n = \overbrace{LL\cdots L}^{n}</math>همچنین <math>L^0 = \{ \epsilon \}</math> تعریف می‌کنیم. توجه کنید که <math>\{ \epsilon \} \neq \varnothing</math>.<ref name=":2" />
* ''[[الفبا (نظریه زبان‌ها)#معکوس رشته|معکوس]]'' <math>L^\mathcal{R}</math> مجموعهٔ معکوس تمام رشته‌های زبان مذکور است: <math>L^\mathcal{R} = \{ w^\mathcal{R} \mid w \in L \}</math>
* [[ستاره کلین|بستار کلین]] <math>L^*</math> به صورت <math>L^* = \bigcup_{n \in \mathbb{N}} L^n = L^0 \cup L^1 \cup L^2 \cup \cdots</math> تعریف می‌کنیم.
* همچنین [[الفبا (نظریه زبان‌ها)#%D8%AA%D9%88%D8%A7%D9%86%20%D8%A7%D9%84%D9%81%D8%A8%D8%A7|بستار مثبت]] <math>L^+</math> را به این شکل تعریف می‌کنیم: <math>L^+ = \bigcup_{n \in \mathbb{N}^\star} L^n = L^1 \cup L^2 \cup \cdots</math>

== توصیف زبان‌ها ==
برای تولید یا توصیف یک زبان از [[دستور زبان قراردادی|گرامر قراردادی]]، [[نظریه اتوماتا|اتوماتا]]، [[عبارت باقاعده|عبارات باقاعده]] {{به انگلیسی|regex}} یا [[مدل محاسباتی|مدل‌های محاسباتی]] استفاده می‌شود.<ref name=":2" />

[[مسئله تصمیم|مسئلهٔ تصمیم]] معادل [[عنصر (ریاضیات)|عضویت]] در یک زبان قراردادی است. مجموعهٔ همهٔ رشته‌هایی که یک اتوماتا می‌پذیرد (یا یک گرامر تولید می‌کند یا با یک عبارت باقاعده تطابق دارند) یک زبان است. همچنین پذیرش یک رشته توسط یک ماشین معادل عضویت آن در زبان مذکور است. بنابراین نظریه زبان‌ها بسیار با [[نظریه ماشین ها|نظریهٔ ماشین‌ها]] مرتبط است و همچنین یک حوزه کاربردی اصلی در [[نظریه رایانش‌پذیری]] و [[نظریه پیچیدگی محاسباتی|نظریهٔ پیچیدگی محاسباتی]] است.<ref name=":2" />

زبان‌های قراردادی را می‌توان به کمک [[وراثت چامسکی]] بر اساس قدرت مولد ([[دستور زبان قراردادی|گرامر]]) آنها یا پیچیدگی [[نظریه اتوماتا|اتوماتای]] تصمیم آنها طبقه‌بندی کرد.

== جستارهای وابسته ==

* [[نظریه زبان]]
* [[رشته (علوم رایانه)]]
* [[تحلیل واژگانی|تحلیل واژگان]]
* [[تجزیه‌کننده]]
* [[نظریه (منطق ریاضی)]]
* [[ماشین مجازی]]

== منابع ==
<references />
{{چپ‌چین}}
* 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|en}} [http://www.amazon.com/Languages-Machines-Introduction-Computer-Science/dp/0321322215]
{{پایان چپ‌چین}}
{{زبان‌ها و دستور زبان‌های قراردادی}}{{منطق ریاضی}}{{علوم رایانه}}
{{منطق}}
{{داده‌های کتابخانه‌ای}}
[[رده:زبان‌های قراردادی]]
[[رده:علوم نظری رایانه]]
[[رده:زبان های قراردادی]]