نظریه زبان‌ها: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
جزبدون خلاصۀ ویرایش |
بازنویسی و حذف اشتباهات + گسترش برچسب‌ها: متن دارای ویکی‌متن نامتناظر ویرایشگر دیداری |
||
خط ۱:
در [[منطق]]، [[ریاضیات]]، [[علوم رایانه|علوم کامپیوتر]] و [[زبان‌شناسی]]، یک '''زبان صوری''' {{به انگلیسی|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> مفهوم [[دستور زبان صوری|گرامر صوری]] شباهت بیشتری به [[زبان طبیعی|تصور انسانی از یک زبان]] دارد. زبانی که با قواعد [[نحو|نحوی]] محدود شده باشد.
== تعاریف پایه ==
{{اصلی|الفبا (نظریه زبان‌ها)}}
[[الفبا (نظریه زبان‌ها)|'''الفبای''' صوری]] مجموعهٔ حروفی (مثل الف، ب، پ و ...) به نام '''نماد''' است که با قرارگیری آنها در کنار هم (الحاقشان) کلماتی به نام '''رشته''' پدید می‌آیند. هر کلمهٔ صوری از به هم پیوستن حروف این الفبا به دست می‌آید. مثلاً کلمهٔ «آب» (با حروف آ + ب) به زبان [[زبان فارسی|فارسی]] تعلق دارد ولی در [[زبان عربی|عربی]] معنا ندارد (با این وجود [[الفبای فارسی|الفبای آنها]] یکسان است). گاهی کلماتی که به یک زبان صوری خاص تعلق دارند ''[[فرمول خوش فرم|جمله یا فرمول‌های خوش‌فرم]]'' نامیده می شوند.<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 \cdot L_2</math> مجموعهٔ تمام رشته‌های حاصل از الحاق اعضای این دو است: <math>L_1 \cdot 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" />
== دسته‌بندی زبان‌های فرمال ==
سطر ۲۳ ⟵ ۳۹:
* [[زبان حساس به متن|زبان‌های حسّاس به متن]]
* [[زبان‌های بدون محدودیت]]{{منبع؟}}
▲== تعریف ==
== جستارهای وابسته ==
* [[نظریه
== منابع ==
<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]
{{پایان چپ‌چین}}
{{زبان‌ها و دستور زبان‌های صوری}}{{منطق ریاضی}}{{علوم رایانه}}
{{منطق}}
{{داده‌های کتابخانه‌ای}}
[[رده:زبان‌های صوری]]
[[رده:علوم نظری رایانه]]
| |||