زبان منظم
![](http://178.128.105.246/content-http-upload.wikimedia.org/wikipedia/commons/thumb/9/9a/Chomsky-hierarchy.svg/220px-Chomsky-hierarchy.svg.png)
در علوم نظری رایانه، زبانهای منظم، به زیرمجموعهای از زبانهای صوری گفته میشود.
اعضای یک زبان منظم با عبارتهای منظم ساختهمیشوند و توسط ماشین حالت متناهی معین پذیرفته میشوند. از زبانهای منظم در تجزیه کنندهها و طراحی زبانهای برنامهنویسی استفاده میشود.
تعریف
[ویرایش]مجموعهٔ زبانهای منظم روی یک الفبا مثل ، به صورت بازگشتی زیر تعریف میشود:
- زبان بدون رشته،، یک زبان منظم است.
- برای هر عضو الفبا، ، مجموعهٔ تکعضوی ، یک زبان منظم است.
- اگر مجموعههای و دو زبان منظم باشند، آنگاه اجتماع آنها ، الحاق آنها وستاره کلین () زبانهای منظم هستند.
- مثال
هر مجموعهای شامل تعداد متناهی رشته یک زبان منظم است. مجوعهٔ تکعضوی شامل رشتهٔ تهی، یک زبان منظم است. به همینترتیب، روی الفبای ، زبانی که شامل تعداد برابر از حروف و باشد، یک زبان منظم است.
یک زبان منظم نیست. یعنی این زبان، زبان مورد پذیرش برای هیچ ماشین حالت متناهی نیست و نمیتوان آن را با عبارتهای منظم بیان کرد. برای نشان دادن آن که یک زبان، منظم نیست، از لم تزریق، استفاده میشود.
بیانهای دیگر
[ویرایش]یک زبان منظم:
- زبان مورد پذیرش یک اتوماتون تعینناپذیر متناهی، (NFA) است.
- زبان مورد پذیرش یک ماشینهای تعینپذیر حالات متناهی، (DFA) است.
- زبان مورد پذیرش یک یک ماشین حالت متناهی متناوب، (AFA) است.
- توسط یک دستور منظم (Regular grammar)، ساختهمیشود.
- توسط یک دستور پیشوندی (Prefix grammar)، ساختهمیشود.
- زبان مورد پذیرش یک ماشین تورینگ است.
- قابل بیان در منطق مرتبهٔ دوم است.
تساویهای جبری برای عبارتهای منظم
[ویرایش]لم تزریق
[ویرایش]ویژگیهای بستاری
[ویرایش]اگر زبانهای 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