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

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

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

یک الفبا معمولاً با (سیگما بزرگ[۱][۲][۳] (گاما بزرگ)[۱] یا نمایش داده می‌شود. اندازهٔ الفبا کاردینالیتهٔ مجموعه است و ممکن است متناهی، شمارا یا حتی ناشمارا باشد.[۱]

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

رشتهویرایش

یک رشته (یا کلمهٔ صوری) در یک الفبا به صورت دنباله‌ای از حروف الفبا تعریف می‌شود. به عنوان مثال، به کمک (الفبای شامل) حروف «الف» تا «ی» می‌توان کلمات فارسی مانند «آب» استفاده کرد. یک الفبای رایج،   الفبای باینری است و « » نمونه ای از یک رشته باینری است. یک رشته معمولاً با   نمایش داده می‌شود. طول رشته   تعداد نمادهای درونش است. رشتهٔ تهی با طول صفر را با  ،[۱]  [۳] (اپسیلون کوچک) یا  [۲] (لاندا کوچک) نمایش می‌دهیم.

اغلب برای خوانایی لازم است که نمادها را در یک الفبا به یک علامت محدود کنیم تا تفسیر هر رشته بدون ابهام باشند. برای مثال، اگر الفبای دو عضوی   باشد، رشتهٔ   مبهم است، زیرا مشخص نیست که   است یا   یا  .

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

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

عملگر الحاق دو رشته   و   با نماد ضرب   نمایش می‌دهیم. البته معمولاً این نماد را حذف می‌کنیم و الحاق را به صورت   نشان می‌دهیم.

به عنوان مثال الحاق   و   برابر   است.

توان رشتهویرایش

با   بار الحاق   در خودش به   می‌رسیم. همچنین   تعریف می‌کنیم.[۲]

معکوس رشتهویرایش

معکوس یک رشته   با نماد   همان حروف صوری به ترتیب عکس است؛ مثلاً  .[۲]

اگر معکوس یک رشته با خودش یکسان باشد   به آن رشته پالیندروم می‌گوییم.

زیررشتهویرایش

اگر   می‌گوییم   (و همچنین  ) زیررشتهٔ   است (  دلخواه و شاید تهی). مثلاً «شنبه» زیررشتهٔ «چهارشنبه‌سوری» است.

به   پیشوند   و به   پسوند   می‌گوییم. به اضافه اگر   باشد آن را پیشوند اکید   می‌نامیم.[۱]

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

اگر برای حروف الفبا یک ترتیب الفبایی (مثل  ) تعریف شده باشد می‌توانیم برای رشته‌ها نیز ترتیب تعریف کنیم. ترتیب لغت‌نامه‌ای (به انگلیسی: lexicographic order) همان ترتیبی است که در فرهنگ‌نامه‌ها استفاده می‌شود. با یک تغییر جزئی در قوانین به ترتیب (به انگلیسی: shortlex order) می‌رسیم. در این ترتیب رشته‌های کوتاهتر باید جایگاه کمتری داشته باشند؛ مثلاً در الفبای  :[۱]

در ترتیب lexicographic:  

در ترتیب shortlex:  

توان الفباویرایش

با اعمال عمل توان بر روی یک الفبا یک زبان به دست می‌آید. اگر   یک الفبا باشد، مجموعهٔ تمام رشته‌های به طول   بر روی الفبای   را به صورت   نمایش می‌دهیم؛ مثلاً اگر   باشد  .[۳]

مجموعهٔ تمام رشته‌های با هر طول (متناهی) را بستار کلین   می‌نامیم:  

هر کدام از رشته‌های عضو   متناهی اند ولی خود   شمارا و نامتناهی است. در مثال فوق  

همچنین بستار مثبت   پس  .[۲]

مجموعهٔ تمام رشته‌های نامتناهی را با نماد   نمایش می‌دهیم (توان امگا در اینجا نماد عدد اردینال است) و  .

جملهویرایش

در تعریف الفبا (هر مجموعهٔ ناتهی) هیچ محدودیتی وجود ندارد. در نتیجه مجموعه‌ای از کلمات (از الفبایی مثل  ) خود می‌تواند الفبای دیگری مثل   فرض شود (مثلاً  ). در برخی حوزه‌ها مثل منطق، الفبای صوری به عنوان واژگان (مجموعهٔ کلمات) و کلمات صوری به عنوان جملات شناخته می شوند. به عبارتی دیگر استعارهٔ حرف/کلمه را می‌شکند و استعارهٔ کلمه/جمله جایگزین آن می‌کند. به طور کلی می‌توان به عناصر (کلمات) عضو یک زبان جمله گفت.[۲]

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

منابعویرایش

  1. ۱٫۰ ۱٫۱ ۱٫۲ ۱٫۳ ۱٫۴ ۱٫۵ ۱٫۶ Introduction to the Theory of Computation (Third Edition). به کوشش Michael Sipser.
  2. ۲٫۰ ۲٫۱ ۲٫۲ ۲٫۳ ۲٫۴ ۲٫۵ ۲٫۶ An Introduction to Formal Languages and Automata (Sixth Edition). به کوشش Peter Linz.
  3. ۳٫۰ ۳٫۱ ۳٫۲ ۳٫۳ Introduction to Automata Theory, Languages, and Computation (Third Edition). به کوشش John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman.