نمایش مبدأ برای الفبا (نظریه زبان‌ها)

در [[زبان صوری|نظریهٔ زبان‌های صوری]]، هر [[مجموعه (ریاضیات)|مجموعهٔ]] ناتهی را '''الفبا''' (الفبای صوری) می‌نامیم و اعضای آن را (مثل [[حرف (زبان‌شناسی)|حروف]]، [[رقم|ارقام]] یا {{کد|[[نویسه (رایانه)|char]]}}) '''نمادهای''' آن الفبا (یا حروف صوری آن) هستند.<ref name=":0">{{یادکرد کتاب|عنوان=Introduction to the Theory of Computation (Third Edition)|کوشش=Michael Sipser|شناسه=978-1-133-18781-3}}</ref>

این نمادها می‌توانند مجموعه‌ای از [[واج]]‌ها باشند (مثل [[الفبای آوانگاری بین‌المللی|IPA]]). همچنین [[قلم (رایانه)|فونت‌ها و قلم‌های رایانه]] (مجموعه‌ای از [[گلیف]]‌ها) را نیز می‌توان طبق این تعریف الفبا نامید.<ref name=":1">{{یادکرد کتاب|عنوان=An Introduction to Formal Languages and Automata (Sixth Edition)|کوشش=Peter Linz|شناسه=978-1-284-07724-7}}</ref> الفبا با این تعریف در طیف وسیعی از زمینه‌ها از جمله [[منطق]]، [[ریاضیات]]، [[علوم کامپیوتر]] و [[زبان‌شناسی]] استفاده می‌شود. [[کدبندی نویسه|کدگذاری نویسه‌ها]] مثل [[اسکی (استاندارد)|ASCII]] از نمونه‌های کاربرد در کامپیوتر است.<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>

یک الفبا معمولاً با <math>\Sigma</math> ([[سیگما|سیگما بزرگ]])،<ref name=":0"/><ref name=":1"/><ref name=":2"/> <math>\Gamma</math> ([[گاما (حرف)|گاما بزرگ]])<ref name=":0"/> یا <math>\mathcal{A}</math> نمایش داده می‌شود. اندازهٔ الفبا [[کاردینالیتی|کاردینالیتهٔ]] مجموعه است و ممکن است [[مجموعه متناهی|متناهی]]، [[مجموعه شمارا|شمارا]] یا حتی [[مجموعه ناشمارا|ناشمارا]] باشد.<ref name=":0"/>

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

== رشته ==
یک ''[[رشته (علوم رایانه)|'''رشته''']] (یا کلمهٔ صوری) در یک الفبا'' به صورت «[[دنباله|دنباله‌ای]] از حروف الفبا» تعریف می‌شود. به عنوان مثال، به کمک (الفبای شامل) [[الفبای فارسی|حروف «الف» تا «ی»]] می‌توان کلمات فارسی مانند «آب» ایجاد کرد. یک الفبای رایج، <math>\Sigma = \{ 0, 1 \}</math> '''الفبای باینری''' است و «<math>w = 00101111</math>» نمونه ای از یک رشته باینری است. یک رشته معمولاً با <math>u, v, w, x, y</math> نمایش داده می‌شود. '''طول رشته''' <math>|w|</math> تعداد نمادهای درونش است. '''رشتهٔ تهی''' با طول صفر را با <math>\varepsilon</math>،<ref name=":0"/> <math>\epsilon</math><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> ([[اپسیلون|اپسیلون کوچک]]) یا <math>\lambda</math><ref name=":1">{{یادکرد کتاب|عنوان=An Introduction to Formal Languages and Automata (Sixth Edition)|کوشش=Peter Linz|شناسه=978-1-284-07724-7}}</ref> ([[لامبدا|لاندا کوچک]]) نمایش می‌دهیم.

اغلب برای خوانایی لازم است که نمادها را در یک الفبا به یک علامت محدود کنیم تا تفسیر هر رشته بدون ابهام باشند. برای مثال، اگر الفبای دو عضوی <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> تعریف می‌کنیم.<ref name=":1" />

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

اگر معکوس یک رشته با خودش یکسان باشد <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> می‌نامیم.<ref name=":0"/>

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

در ترتیب 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>.<ref name=":2" />

مجموعهٔ تمام رشته‌های با هر طول (متناهی) را [[ستاره کلین|بستار کلین <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>.<ref name=":1" />

مجموعهٔ تمام رشته‌های نامتناهی را با نماد <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>). در برخی حوزه‌ها مثل [[منطق ریاضی|منطق]]، الفبای صوری به عنوان ''واژگان (مجموعهٔ کلمات)'' و کلمات صوری به عنوان ''جملات'' شناخته می شوند. به عبارتی دیگر استعارهٔ حرف/کلمه را می‌شکند و استعارهٔ کلمه/جمله جایگزین آن می‌کند. به طور کلی می‌توان به عناصر (کلمات) عضو یک [[زبان صوری|زبان]] جمله گفت.<ref name=":1" />

== جستارهای وابسته ==
* [[فهرست نمادهای ریاضی]]

== منابع ==
{{پانویس|۲}}
[[رده:زبان‌های صوری]]