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

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

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

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

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

رشته

یک رشته (یا کلمهٔ صوری) در یک الفبا به صورت «دنباله‌ای از حروف الفبا» تعریف می‌شود. به عنوان مثال، به کمک (الفبای شامل) حروف «الف» تا «ی» می‌توان کلمات فارسی مانند «آب» ایجاد کرد. یک الفبای رایج، $\mathrm{\Sigma }=\{0,1\}$ الفبای باینری است و «$w=00101111$» نمونه ای از یک رشته باینری است. یک رشته معمولاً با $u,v,w,x,y$ نمایش داده می‌شود. طول رشته $|w|$ تعداد نمادهای درونش است. رشتهٔ تهی با طول صفر را با $\epsilon$، $ϵ$ (اپسیلون کوچک) یا $\lambda$ (لاندا کوچک) نمایش می‌دهیم.

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

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

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

الگو:اصلی عملگر الحاق دو رشته $v$ و $w$ با نماد ضرب $v\cdot w$ نمایش می‌دهیم. البته معمولاً این نماد را حذف می‌کنیم و الحاق را به صورت $vw$ نشان می‌دهیم.

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

توان رشته

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

معکوس رشته

معکوس یک رشته $u$ با نماد $u^{ℛ}$ همان حروف صوری به ترتیب عکس است؛ مثلاً $(vw{)}^{ℛ}=1110$.

اگر معکوس یک رشته با خودش یکسان باشد $u^{ℛ}=u$ به آن رشته پالیندروم می‌گوییم.

زیررشته

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

به $v$ پیشوند $z$ و به $u$ پسوند $z$ می‌گوییم. به اضافه اگر $v\ne z$ باشد آن را پیشوند اکید $z$ می‌نامیم.

ترتیب رشته‌ها

اگر برای حروف الفبا یک ترتیب الفبایی (مثل $a⩽b⩽\cdots$) تعریف شده باشد می‌توانیم برای رشته‌ها نیز ترتیب تعریف کنیم. ترتیب لغت‌نامه‌ای الگو:به انگلیسی همان ترتیبی است که در فرهنگ‌نامه‌ها استفاده می‌شود. با یک تغییر جزئی در قوانین به ترتیب الگو:به انگلیسی می‌رسیم. در این ترتیب رشته‌های کوتاهتر باید جایگاه کمتری داشته باشند؛ مثلاً در الفبای $\mathrm{\Sigma }=\{0,1\}$:

در ترتیب lexicographic: $ϵ<0<00<000<01<1<10<11$

در ترتیب shortlex: $ϵ<0<1<00<01<10<11<000$

توان الفبا

با اعمال عمل توان بر روی یک الفبا یک زبان به دست می‌آید. اگر $\mathrm{\Sigma }$ یک الفبا باشد، مجموعهٔ تمام رشته‌های به طول $n$ بر روی الفبای $\mathrm{\Sigma }$ را به صورت ${\mathrm{\Sigma }}^n$ نمایش می‌دهیم؛ مثلاً اگر $\mathrm{\Sigma }=\{0,1\}$ باشد ${\mathrm{\Sigma }}^0=\{ϵ\},{\mathrm{\Sigma }}^1=\mathrm{\Sigma },{\mathrm{\Sigma }}^2=\{00,01,10,11\}$.

مجموعهٔ تمام رشته‌های با هر طول (متناهی) را بستار کلین $\mathrm{\Sigma }$ می‌نامیم: ${\mathrm{\Sigma }}^{*}=\bigcup _{n\in \mathbb{N}}{\mathrm{\Sigma }}^n={\mathrm{\Sigma }}^0\cup {\mathrm{\Sigma }}^1\cup {\mathrm{\Sigma }}^2\cup \cdots$

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

همچنین بستار مثبت ${\mathrm{\Sigma }}^{+}=\bigcup _{n\in {\mathbb{N}}^{\star }}{\mathrm{\Sigma }}^n={\mathrm{\Sigma }}^{*}\mathrm{\setminus }\{ϵ\}$ پس ${\mathrm{\Sigma }}^{*}={\mathrm{\Sigma }}^{+}\cup \{ϵ\}$.

مجموعهٔ تمام رشته‌های نامتناهی را با نماد ${\mathrm{\Sigma }}^{\omega }$ نمایش می‌دهیم (توان امگا در اینجا نماد عدد اردینال است) و ${\mathrm{\Sigma }}^{\mathrm{\infty }}={\mathrm{\Sigma }}^{*}\cup {\mathrm{\Sigma }}^{\omega }$.

جمله

در تعریف الفبا (هر مجموعهٔ ناتهی) هیچ محدودیتی وجود ندارد. در نتیجه مجموعه‌ای از کلمات (از الفبایی مثل $\mathrm{\Sigma }$) خود می‌تواند الفبای دیگری مثل $𝒜$ فرض شود (مثلاً $𝒜={\mathrm{\Sigma }}^2$). در برخی حوزه‌ها مثل منطق، الفبای صوری به عنوان واژگان (مجموعهٔ کلمات) و کلمات صوری به عنوان جملات شناخته می شوند. به عبارتی دیگر استعارهٔ حرف/کلمه را می‌شکند و استعارهٔ کلمه/جمله جایگزین آن می‌کند. به طور کلی می‌توان به عناصر (کلمات) عضو یک زبان جمله گفت.

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

• فهرست نمادهای ریاضی