نظریه زبان‌ها: تفاوت میان نسخه‌ها
جز اصلاح پیوندها |
جز افزودن جستارهای وابسته |
||
| خط ۳۶: | خط ۳۶: | ||
یک زبان صوری <math>L \!</math> برروی یک الفبای <math>\Sigma \!</math> عبارت است از یک زیرمجموعه از <math>\Sigma^{*} \!</math> |
یک زبان صوری <math>L \!</math> برروی یک الفبای <math>\Sigma \!</math> عبارت است از یک زیرمجموعه از <math>\Sigma^{*} \!</math> |
||
== جستارهای وابسته == |
|||
* [[نظریه اتوماتا]] |
|||
* [[ماشین‌های تورینگ]] |
|||
== پانوشته‌ها == |
== پانوشته‌ها == |
||
نسخهٔ ۱۴ ژوئیهٔ ۲۰۱۶، ساعت ۱۸:۳۰
زبان صوری یا زبان فُرمال در ریاضیات، منطق و علوم رایانه، به زبانی‌هایی گفته می‌شود، که با فرمول‌های دقیقِ ریاضیاتی و قابلیت پردازش برای ماشین تعریف شده‌اند.
به طور کلی در این رشته‌ها، زبان‌ها به دو دستهٔ فرمال و طبیعی تقسیم‌بندی می‌شوند. زبان‌های فرمال زبان‌هایی هستند که توسط گرامرها تولید می‌شوند یا ماشینی برای ارزیابی آنها وجود دارد.
تعاریف پایه
- نماد: کوچک‌ترین و بنیادی‌ترین عضو یک زبان است. برخی مواقع به نمادها حرف هم گفته می‌شود. نمادها را معمولاً با حروف لاتین کوچک مثل 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 [۱]
