زبان منظم

Chomsky-hierarchy

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

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

تعریف

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

• زبان بدون رشته،$\mathrm{\varnothing }$، یک زبان منظم است.
• برای هر عضو الفبا، $a\in \mathrm{\Sigma }$، مجموعهٔ تک‌عضوی $\{a\}$، یک زبان منظم است.
• اگر مجموعه‌های $A$ و $B$ دو زبان منظم باشند، آنگاه اجتماع آن‌ها $(A\cup B)$، الحاق آن‌ها $(A\cap B)$ وستاره کلین ($A^{*}$) زبان‌های منظم هستند.

مثال

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

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

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

یک زبان منظم:

• زبان مورد پذیرش یک اتوماتون تعین‌ناپذیر متناهی، (NFA) است.
• زبان مورد پذیرش یک ماشین‌های تعین‌پذیر حالات متناهی، (DFA) است.
• زبان مورد پذیرش یک یک ماشین حالت متناهی متناوب، (AFA) است.
• توسط یک دستور منظم (Regular grammar)، ساخته‌می‌شود.
• توسط یک دستور پیشوندی (Prefix grammar)، ساخته‌می‌شود.
• زبان مورد پذیرش یک ماشین تورینگ است.
• قابل بیان در منطق مرتبهٔ دوم است.

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

• $(R^{*}{)}^{*}=R^{*}$
• $(ϵ+R{)}^{*}=R^{*}$
• $R+R^{*}=R^{*}$
• $R{R}^{*}=R^{+}$

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

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

• اجتماع دو زبان، یعنی $M\cup N$ منظم است.
• الحاق آن دو، $M\circ N$ منظم است.
• اشتراک آن‌ها، یعنی $M\hat{N}$ منظم است.
• ستاره کلین هر کدام از آن‌ها، $M^{*}$ و $N^{*}$ منظم‌اند.
• تفریق و متمم آن‌ها،$M-N$ و $\overline{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