نظریه زبان‌ها

## زبان فرمالیسم |زبان قراردادی |زبان صوری

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

نظریهٔ زبان‌ها به عنوان راهی برای درک قوانین نحوی زبان‌های طبیعی از زبان‌شناسی سرچشمه گرفت و نوام چامسکی در پیشرفت آن نقش مؤثری داشت. در علوم کامپیوتر، زبان‌های قراردادی به عنوان مبنایی برای تعریف دستور زبان‌های برنامه‌نویسی استفاده می‌شوند. در نظریهٔ پیچیدگی محاسباتی، مسائل تصمیم معمولاً به عنوان زبان‌های قراردادی تعریف می‌شوند و کلاس‌های پیچیدگی به عنوان مجموعه‌ای از زبان‌های قراردادی تعریف می‌شوند که می‌توانند توسط ماشین‌های تجزیه‌گر تجزیه شوند. در منطق، فرمالیسم ریاضی و مبانی ریاضی، از زبان‌های قراردادی برای تعریف دقیق نحو ماشین های مجازی همچون نظریهٔ مجموعه‌ها استفاده می‌شود.

یک **زبان قراردادی**  شامل کلماتی است متشکل از حروف یک الفبا که بر اساس قوانینی به صورت خوش‌ساخت شکل بگیرند.

در علوم کامپیوتر و ریاضیات که معمولاً با زبان‌های طبیعی سروکار ندارند، صفت «قراردادی» حذف می شود. مفهوم گرامر قراردادی شباهت بیشتری به تصور انسانی از یک زبان دارد. زبانی که با قواعد نحوی محدود شده باشد.

## تعاریف پایه

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

## زبان قراردادی | صوری
هر مجموعه‌ای از رشته‌ها (یا کلمات) از یک الفبای خاص \Sigma را یک **زبان قراردادی** L در \Sigma (یا بر روی \Sigma) می‌نامیم. به عبارتی دیگر L \subseteq \Sigma^* است.

با این تعریف مجموعهٔ تهی نیز یک زبان (زبان تهی بر روی هر \Sigma دلخواه) محسوب می‌شود. در یک زبان لزومی ندارد که از همهٔ حروف الفبا استفاده شود.

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

### اعمال روی زبان‌ها
ماهیت زبان‌ها مجموعه است؛ در نتیجه اعمال مجموعه‌ها (تفاضل، اجتماع، اشتراک و تفاضل متقارن) روی آنها نیز تعریف می‌شود:

* کاردینالیتی (تعداد اعضای) اکثر زبان‌ها بی‌نهایت است.
* '''متمم''' یک زبان L روی الفبای \Sigma برابر است با \overline{L} = \Sigma^* \backslash L.

همچنین اعمال روی رشته‌ها و الفبا نیز روی زبان‌ها قابل تعمیم است:

* *[[الفبا (نظریه زبان‌ها)#%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|الحاق]]* L_1 \circ L_2 مجموعهٔ تمام رشته‌های حاصل از الحاق اعضای این دو است: L_1 \cdot L_2 = L_1 L_2 = \{ vw : v \in L_1 \and w \in L_2 \}
* توان L^n با n بار الحاق L در خودش به دست می‌آید: L^n = \overbrace{LL\cdots L}^{n}همچنین L^0 = \{ \epsilon \} تعریف می‌کنیم. توجه کنید که \{ \epsilon \} \neq \varnothing.
* *[[الفبا (نظریه زبان‌ها)#معکوس رشته|معکوس]]* L^\mathcal{R} مجموعهٔ معکوس تمام رشته‌های زبان مذکور است: L^\mathcal{R} = \{ w^\mathcal{R} \mid w \in L \}
* بستار کلین L^* به صورت L^* = \bigcup_{n \in \mathbb{N}} L^n = L^0 \cup L^1 \cup L^2 \cup \cdots تعریف می‌کنیم.
* همچنین بستار مثبت L^+ را به این شکل تعریف می‌کنیم: L^+ = \bigcup_{n \in \mathbb{N}^\star} L^n = L^1 \cup L^2 \cup \cdots

## توصیف زبان‌ها
برای تولید یا توصیف یک زبان از گرامر قراردادی، اتوماتا، عبارات باقاعده  یا مدل‌های محاسباتی استفاده می‌شود.

مسئلهٔ تصمیم معادل عضویت در یک زبان قراردادی است. مجموعهٔ همهٔ رشته‌هایی که یک اتوماتا می‌پذیرد (یا یک گرامر تولید می‌کند یا با یک عبارت باقاعده تطابق دارند) یک زبان است. همچنین پذیرش یک رشته توسط یک ماشین معادل عضویت آن در زبان مذکور است. بنابراین نظریه زبان‌ها بسیار با نظریهٔ ماشین‌ها مرتبط است و همچنین یک حوزه کاربردی اصلی در نظریه رایانش‌پذیری و نظریهٔ پیچیدگی محاسباتی است.

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

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

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

## منابع

* Sudkamp, T. A. , *An Introduction to the Theory of Computer Science, Languages and Machines*, 3rd ed. , Pearson Education, Inc. , 2006.  http://www.amazon.com/Languages-Machines-Introduction-Computer-Science/dp/0321322215

رده:زبان‌های صوری
رده:علوم نظری رایانه