زبان منظم

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

در علوم نظری رایانه، زبان‌های منظم، به زیرمجموعه‌ای از زبان‌های صوری گفته‌ می‌شود.

اعضای یک زبان منظم با عبارت‌های منظم ساخته‌می‌شوند و توسط ماشین حالت متناهی معین پذیرفته می‌شوند. از زبان‌های منظم در تجزیه کننده‌ها و طراحی زبان‌های برنامه‌نویسی استفاده می‌شود.

تعریف[ویرایش]

مجموعه‌ی زبان‌های منظم روی یک الفبا مثل ∑، به صورت بازگشتی زیر تعریف می‌شود:

  • زبان بدون رشته،∅، یک زبان منظم است.
  • برای هر عضو الفبا، ∑∋a، مجموعه‌ی تک‌عضوی {a}، یک زبان منظم است.
  • اگر مجموعه‌های Aو B دو زبان منظم باشند، آنگاه اجتماع آن‌ها (ABالحاق آن‌ها (AB) وستاره کلین (*A) زبان‌های منظم هستند.
مثال

هر مجموعه‌ای شامل رشته‌هایی با طول متناهی یک زبان منظم است. مجوعه‌ی تک‌عضوی شامل رشته‌ی تهی، {\epsilon} یک زبان منظم است. به همین‌ترتیب، روی الفبای \{a,b\}^*، زبانی که شامل تعداد برابر از حروف a و b باشد، یک زبان منظم است.

\{a^nb^n|n\geq 0\} یک زبان منظم نیست. یعنی این زبان، زبان مورد پذیرش برای هیچ ماشین حالت متناهی نیست و نمی‌توان آن را با عبارت‌های منظم بیان کرد. برای نشان دادن آن که یک زبان، منظم نیست، از لم تزریق، استفاده می‌شود.

بیان‌های دیگر[ویرایش]

یک زبان منظم:

تساوی‌های جبری برای عبارت‌های منظم[ویرایش]

  • (R^*)^*=R^*
  • (\epsilon + R)^*=R^*
  • R+R^*=R^*
  • RR^*=R^+

لم تزیق[ویرایش]

ویژگی‌های بستاری[ویرایش]

اگر زبان‌های M و N، منظم باشند:

  • اجتماع دو زبان، یعنی M\cup N منظم است.
  • الحاق آن‌‌ دو، M \circ N منظم است.
  • اشتراک آن‌ها، یعنی M\hat N منظم است.
  • ستاره کلین هر کدام از آن‌ها، M^* و N^* منظم‌اند.
  • تفریق و متمم آن‌ها،M-N و \bar{M} منظم‌اند.
  • معکوس زبان‌، M^R، منظم است.

ویژگی‌های تصمیمی[ویرایش]

ویژگی‌های تصمیمی سؤالهایی است که درباره‌ی یک اتوماتا یا یک زبان می‌توانیم بپرسیم. در زیر نمونه‌ای از آنها را مشاهده می‌کنید.

  • مسأله عضویت

آیا رشته‌ی w متعلق به زبان L است؟

  • مسأله تهی بودن

آیا زبان L تهی است؟ برای پاسخ به این سؤال باید به این سؤال جواب داد که آیا مسیری در اتوماتای A که زبان L را می‌پذیرد وجود دارد که ما را از یک حالت آغازین به یک حالت پایانی برساند؟

  • مسأله متناهی بودن

آیا در زبان L تعداد محدودی رشته وجود دارد؟ برای پاسخ به سؤال ذکر شده دو راهکار یا لم وجود دارد. لم1: اگر DFA دارای n حالت باشد و رشته‌ای با طول n یا بیشتر را بپذیرد، آنگاه زبان DFA نامتناهی است. لم2: اگر رشته‌ای با طول n یا بیشتر در زبان L (که DFAی معادلی با n حالت دارد) وجود داشته باشد، آنگاه رشته‌ای با طول بین n و 2n-1 نیز دارد.

زیرمجموعه‌ها[ویرایش]

  • زبان‌های متناهی، که مجموعه‌هایی شامل تعداد متناهی رشته‌ هستند.
  • زبان‌های بی‌ستاره، شامل رشته‌هایی که توسط عبارت‌های منظم، از رشته‌های تهی، نماد‌های الفبا و اعمال جبری و الحاق روی آن‌ها به دست می‌آیند. از ستاره کلین نمی‌توان در آن‌ها استفاده کرد. این دسته از زبان‌ها، شامل همه‌ی زبان‌های متناهی‌اند.

منابع[ویرایش]

An Introduction to Formal Languages and Automata، Peter Linz

Introduction to the Theory of Computation، Michael Sipser