تفاوت میان نسخه‌های «زبان صوری»

۲۸ بایت اضافه‌شده ،  ۵ سال پیش
جز
ویرایش و ویکی‌سازی جزئی
جز (ویرایش و ویکی‌سازی جزئی)
'''زبان صوری''' در [[ریاضیات]]، [[منطق]] و دانش [[رایانه]]، به زبانی که با فرمول‌های دقیقدقیقِ ریاضیاتی و قابل پردازش برای ماشین تعریف شداند،شده‌اند، '''زبان‌های فُرمال''' یا '''زبان‌های صوری''' گفته می‌شود.
 
به طور کلیبه‌طورکلی در این رشته‌ها، زبان‌ها به دو دستهدستهٔ فرمال و طبیعی تقسیم بندیتقسیم‌بندی می‌شوند . زبان‌های فرمال زبان هاییزبان‌هایی هستند که توسط گرامرها تولید می‌شوند یا ماشینی برای ارزیابی آنها وجود دارد .
 
== تعاریف پایه ==
* [[نماد]] : کوچک‌ترین و بنیادی‌ترین عضو یک زبان است . برخی مواقع به نمادها حرف هم گفته می‌شود . نمادها را معمولاً با حروف لاتین کوچک مثل a ، b و ... نشان می‌دهند .
* الفبا : یک مجموعه متناهی از نمادها که در یک زبان تعریف شده‌اند . الفبای زبان توسط Σ نشان داده می‌شود .
* رشته : دنباله‌ای از نمادهای یک مجموعه الفباست که با عمل الحاق به هم پیوسته‌اند .
 
رشته ممکن است متناهی یا غیر متناهی باشد . طول یک رشته برابر است با تعداد نمادهایی که رشته را تشکیل می‌دهند . طول رشته را با قدر مطلق آن نمایش می‌دهند . مثلاً :
 
اگر w=aabbbbc آنگاه طول رشته ( |w| ) برابر است با هفت . زیرا این رشته با هفت نماد ساخته شده است شده‌است.
* زبان : مجموعه‌ای از رشته‌ها است رشته‌هاست. این مجموعه می‌تواند متناهی، نامتناهی شمارا یا نامتناهی ناشمارا باشد .
 
زبان بدون رشته را با Ø نشان می‌دهند .
 
رشته‌ای به طول صفر را با λ یا ε نشان می‌دهند . آن را [[رشته تهی|رشتهٔ تهی]] می نامند می‌نامند.
 
== دسته‌بندی زبان‌های فرمال ==
 
زبان‌های فرمال به چهار دسته تقسیم می‌شوند :
* [[زبان‌های منظم]]
* [[زبان‌های مستقل از متن]]
== عملگرهای روی زبان‌های فرمال ==
 
زبان مجموعه‌ای از رشته هاست رشته‌هاست. بنابر این ماهیت زبان‌ها، مجموعه است . همههمهٔ عملگر هاییعملگرهایی که روی مجموعه‌ها تعریف شده اند مانند اجتماع، اشتراک، متمم، تفاضل و ... روی زبان‌ها قابل تعریف هستند .
 
[[الحاق (نظریه ماشین‌ها)|عملگر الحاق]] که روی رشته‌ها تعریف شده است،شده‌است، روی زبان‌ها نیز قابل تعریف است .
 
عملگرهای دیگری مانند عمل معکوس سازیمعکوس‌سازی ( Reverse ) نیز روی رشته‌های زبان قابل تعریف است .
 
== تعریف ==
 
یک زبان صوری <math>L \!</math> برروی یک الفبای <math>\Sigma \!</math> عبارت است از یک زیر مجموعهزیرمجموعه از <math>\Sigma^{*} \!</math>
 
== پانوشته‌ها ==
۴۹٬۷۹۷

ویرایش