نظریه زبان‌ها: تفاوت میان نسخه‌ها

از ویکی‌پدیا، دانشنامهٔ آزاد
محتوای حذف‌شده محتوای افزوده‌شده
AliBot (بحث | مشارکت‌ها)
جز ربات:اصلاح فاصلهٔ مجازی
Amirobot (بحث | مشارکت‌ها)
جز ربات: تصحیح جایگذاری کاما، شمارگان هزارگان
خط ۱۷: خط ۱۷:
اگر w=aabbbbc آنگاه طول رشته ( |w| ) برابر است با هفت . زیرا این رشته با هفت نماد ساخته شده است .
اگر w=aabbbbc آنگاه طول رشته ( |w| ) برابر است با هفت . زیرا این رشته با هفت نماد ساخته شده است .


* زبان : مجموعه‌ای از رشته‌ها است . این مجموعه می‌تواند متناهی ، نامتناهی شمارا یا نامتناهی ناشمارا باشد .
* زبان : مجموعه‌ای از رشته‌ها است . این مجموعه می‌تواند متناهی، نامتناهی شمارا یا نامتناهی ناشمارا باشد .


زبان بدون رشته را با Ø نشان می‌دهند .
زبان بدون رشته را با Ø نشان می‌دهند .
خط ۳۵: خط ۳۵:
== عملگرهای روی زبان‌های فرمال ==
== عملگرهای روی زبان‌های فرمال ==


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


[[الحاق (نظریه ماشین‌ها)|عملگر الحاق]] که روی رشته‌ها تعریف شده است ، روی زبان‌ها نیز قابل تعریف است .
[[الحاق (نظریه ماشین‌ها)|عملگر الحاق]] که روی رشته‌ها تعریف شده است، روی زبان‌ها نیز قابل تعریف است .


عملگرهای دیگری مانند عمل معکوس سازی ( Reverse ) نیز روی رشته‌های زبان قابل تعریف است .
عملگرهای دیگری مانند عمل معکوس سازی ( Reverse ) نیز روی رشته‌های زبان قابل تعریف است .

نسخهٔ ‏۱۷ فوریهٔ ۲۰۱۱، ساعت ۲۰:۳۰

در ریاضیات، منطق و دانش رایانه، به زبانی که با فرمول‌های دقیق ریاضیاتی و قابل پردازش برای ماشین تعریف شداند، زبان‌های فُرمال یا زبان‌های صوری گفته می‌شود.

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


تعاریف پایه

  • نماد : کوچک‌ترین و بنیادی‌ترین عضو یک زبان است . برخی مواقع به نمادها حرف هم گفته می‌شود . نمادها را معمولاً با حروف لاتین کوچک مثل a ، b و ... نشان می‌دهند .
  • الفبا : یک مجموعه متناهی از نمادها که در یک زبان تعریف شده اند . الفبای زبان توسط Σ نشان داده می‌شود .
  • رشته : دنباله‌ای از نمادهای یک مجموعه الفباست که با عمل الحاق به هم پیوسته اند .

رشته ممکن است متناهی یا غیر متناهی باشد . طول یک رشته برابر است با تعداد نمادهایی که رشته را تشکیل می‌دهند . طول رشته را با قدر مطلق آن نمایش می‌دهند . مثلاً :

اگر w=aabbbbc آنگاه طول رشته ( |w| ) برابر است با هفت . زیرا این رشته با هفت نماد ساخته شده است .

  • زبان : مجموعه‌ای از رشته‌ها است . این مجموعه می‌تواند متناهی، نامتناهی شمارا یا نامتناهی ناشمارا باشد .

زبان بدون رشته را با Ø نشان می‌دهند .

رشته‌ای به طول صفر را با λ یا ε نشان می‌دهند . آن را رشته تهی می نامند .

دسته‌بندی زبان‌های فرمال

زبان‌های فرمال به چهار دسته تقسیم می‌شوند :


عملگرهای روی زبان‌های فرمال

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

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

عملگرهای دیگری مانند عمل معکوس سازی ( Reverse ) نیز روی رشته‌های زبان قابل تعریف است .

تعریف

یک زبان صوری برروی یک الفبای عبارت است از یک زیر مجموعه از

پانوشته‌ها


منابع

An Introduction to Formal Languages and Automata, Peter Linz

  • Sudkamp, T. A., An Introduction to the Theory of Computer Science, Languages and Machines, 3rd ed., Pearson Education, Inc., 2006. ISBN 0-321-32221-5 [۱]