الفبا (نظریه زبان‌ها)

در نظریهٔ زبان‌های صوری، هر مجموعهٔ ناتهی را **الفبا** (الفبای صوری) می‌نامیم و اعضای آن را (مثل حروف، ارقام یا ) **نمادهای** آن الفبا (یا حروف صوری آن) هستند.

این نمادها می‌توانند مجموعه‌ای از واج‌ها باشند (مثل IPA). همچنین فونت‌ها و قلم‌های رایانه (مجموعه‌ای از گلیف‌ها) را نیز می‌توان طبق این تعریف الفبا نامید. الفبا با این تعریف در طیف وسیعی از زمینه‌ها از جمله منطق، ریاضیات، علوم کامپیوتر و زبان‌شناسی استفاده می‌شود. کدگذاری نویسه‌ها مثل ASCII از نمونه‌های کاربرد در کامپیوتر است.

یک الفبا معمولاً با \Sigma (سیگما بزرگ)، \Gamma (گاما بزرگ) یا \mathcal{A} نمایش داده می‌شود. اندازهٔ الفبا کاردینالیتهٔ مجموعه است و ممکن است متناهی، شمارا یا حتی ناشمارا باشد.

الفبا در نظریه زبان‌ها و نظریه ماشین‌ها مهم هستند. برای تعریف اتوماتاهایی مثل DFA لازم است الفبایی مشخص کنیم تا رشته‌های ورودی آن اتوماتا از آن رشته‌ها باشند.

## رشته
یک *[[رشته (علوم رایانه)|*'رشته**]] (یا کلمهٔ صوری) در یک الفبا'' به صورت «[[دنباله|دنباله‌ای]] از حروف الفبا» تعریف می‌شود. به عنوان مثال، به کمک (الفبای شامل) [[الفبای فارسی|حروف «الف» تا «ی»]] می‌توان کلمات فارسی مانند «آب» ایجاد کرد. یک الفبای رایج، <math>\Sigma = \{ 0, 1 \}</math> **الفبای باینری** است و «<math>w = 00101111</math>» نمونه ای از یک رشته باینری است. یک رشته معمولاً با <math>u, v, w, x, y</math> نمایش داده می‌شود. **طول رشته** <math>|w|</math> تعداد نمادهای درونش است. **رشتهٔ تهی** با طول صفر را با <math>\varepsilon</math>، <math>\epsilon</math> ([[اپسیلون|اپسیلون کوچک]]) یا <math>\lambda</math> ([[لامبدا|لاندا کوچک]]) نمایش می‌دهیم.

اغلب برای خوانایی لازم است که نمادها را در یک الفبا به یک علامت محدود کنیم تا تفسیر هر رشته بدون ابهام باشند. برای مثال، اگر الفبای دو عضوی <math>\Gamma = \{ 0, 00 \}</math> باشد، رشتهٔ <math>000</math> مبهم است، زیرا مشخص نیست که <math>0 + 0 + 0</math> است یا <math>0 + 00</math> یا <math>00 + 0</math>.

=== اعمال روی رشته‌ها ===

==== الحاق رشته‌ها ====

[[عملگر (ریاضیات)|عملگر]] الحاق دو رشته <math>v</math> و <math>w</math> با نماد [[فضای ضرب داخلی|ضرب]] <math>v \cdot w</math> نمایش می‌دهیم. البته معمولاً این نماد را [[حذف به قرینه|حذف]] می‌کنیم و الحاق را به صورت <math>vw</math> نشان می‌دهیم.

به عنوان مثال الحاق <math>v = 01</math> و <math>w = 11</math> برابر <math>vw = 0111</math> است.

==== توان رشته ====
با <math>n</math> بار الحاق <math>v</math> در خودش به <math>v^n = \overbrace{vv\cdots v}^{n}</math> می‌رسیم. همچنین <math>v^0 = \epsilon</math> تعریف می‌کنیم.

==== معکوس رشته ====
معکوس یک رشته <math>u</math> با نماد <math>u^\mathcal R</math> همان حروف صوری به ترتیب عکس است؛ مثلاً <math>(vw)^\mathcal{R} = 1110</math>.

اگر معکوس یک رشته با خودش یکسان باشد <math>u^\mathcal R = u</math> به آن رشته [[واروخوانه|پالیندروم]] می‌گوییم.

=== زیررشته ===
اگر <math>z = vwu</math> می‌گوییم <math>w</math> (و همچنین <math>v,\ u</math>) زیررشتهٔ <math>z</math> است (<math>v,\ u</math> دلخواه و شاید تهی). مثلاً «شنبه» زیررشتهٔ «چهارشنبه‌سوری» است.

به <math>v</math> [[پیشوند]] <math>z</math> و به <math>u</math> [[پسوند]] <math>z</math> می‌گوییم. به اضافه اگر <math>v \neq z</math> باشد آن را پیشوند اکید <math>z</math> می‌نامیم.

=== ترتیب رشته‌ها ===
اگر برای حروف الفبا یک ''[[ترتیب کلی|ترتیب]] الفبایی'' (مثل <math>a \leqslant b \leqslant \cdots</math>) تعریف شده باشد می‌توانیم برای رشته‌ها نیز ترتیب تعریف کنیم. ترتیب لغت‌نامه‌ای ** ** همان ترتیبی است که در [[فرهنگ لغت|فرهنگ‌نامه‌ها]] استفاده می‌شود. با یک تغییر جزئی در قوانین به ترتیب ** *' می‌رسیم. در این ترتیب رشته‌های کوتاهتر باید جایگاه کمتری داشته باشند؛ مثلاً در الفبای <math>\Sigma = \{ 0, 1 \}</math>:

در ترتیب lexicographic: <math>\epsilon < 0 < 00 < 000 < 01 < 1 < 10 < 11</math>

در ترتیب shortlex: <math>\epsilon < 0 < 1 < 00 < 01 < 10 < 11 < 000</math>

== توان الفبا ==
با اعمال عمل توان بر روی یک الفبا یک [[زبان صوری|زبان]] به دست می‌آید. اگر <math>\Sigma</math> یک الفبا باشد، مجموعهٔ تمام رشته‌های به طول <math>n</math> بر روی الفبای <math>\Sigma</math> را به صورت <math>\Sigma^n</math> نمایش می‌دهیم؛ مثلاً اگر <math>\Sigma = \{ 0, 1 \}</math> باشد <math>\Sigma^0 = \{ \epsilon \}, \quad \Sigma^1 = \Sigma, \quad \Sigma^2 = \{ 00, 01, 10, 11 \}</math>.

مجموعهٔ تمام رشته‌های با هر طول (متناهی) را [[ستاره کلین|بستار کلین <math>\Sigma</math>]] می‌نامیم: <math>\Sigma^* = \bigcup_{n \in \mathbb{N}} \Sigma^n = {\Sigma^0 \cup \Sigma^1 \cup \Sigma^2 \cup \cdots}</math>

هر کدام از رشته‌های عضو <math>\Sigma^*</math> متناهی اند ولی خود <math>\Sigma^*</math> شمارا و نامتناهی است. در مثال فوق <math>\Sigma^* = \{ \epsilon, 0, 1, 00, 01, 10, 11, \dots \}</math>

همچنین بستار مثبت <math>\Sigma^+ = \bigcup_{n \in \mathbb{N}^\star} \Sigma^n = \Sigma^* \backslash \{ \epsilon \}</math> پس <math>\Sigma^* = \Sigma^+ \cup \{ \epsilon \}</math>.

مجموعهٔ تمام رشته‌های نامتناهی را با نماد <math>\Sigma^\omega</math> نمایش می‌دهیم (توان امگا در اینجا نماد [[عدد ترتیبی|عدد اردینال]] است) و <math>\Sigma^{\infty} = \Sigma^* \cup \Sigma^\omega</math>.

== جمله ==
در تعریف الفبا (هر مجموعهٔ ناتهی) هیچ محدودیتی وجود ندارد. در نتیجه [[زبان صوری|مجموعه‌ای از کلمات]] (از الفبایی مثل <math>\Sigma</math>) خود می‌تواند الفبای دیگری مثل <math>\mathcal{A}</math> فرض شود (مثلاً <math>\mathcal{A} = \Sigma^2</math>). در برخی حوزه‌ها مثل [[منطق ریاضی|منطق]]، الفبای صوری به عنوان *واژگان (مجموعهٔ کلمات)* و کلمات صوری به عنوان *جملات'' شناخته می شوند. به عبارتی دیگر استعارهٔ حرف/کلمه را می‌شکند و استعارهٔ کلمه/جمله جایگزین آن می‌کند. به طور کلی می‌توان به عناصر (کلمات) عضو یک زبان جمله گفت.

## جستارهای وابسته
* فهرست نمادهای ریاضی

## منابع

رده:زبان‌های صوری