زبان منظم

(تغییرمسیر از زبان‌های منظم)

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

Chomsky-hierarchy

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

تعریف

ویرایش

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

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

هر مجموعه‌ای شامل تعداد متناهی رشته یک زبان منظم است. مجوعهٔ تک‌عضوی شامل رشتهٔ تهی،   یک زبان منظم است. به همین‌ترتیب، روی الفبای  ، زبانی که شامل تعداد برابر از حروف   و   باشد، یک زبان منظم است.

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

بیان‌های دیگر

ویرایش

یک زبان منظم:

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

ویرایش
  •  
  •  
  •  
  •  

لم تزریق

ویرایش

ویژگی‌های بستاری

ویرایش

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

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

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

  • مسئله عضویت

آیا رشتهٔ 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