نظریه زبانها: تفاوت میان نسخهها
جز ربات اصلاح: bg:Формален език (математика) |
جز ربات افزودن: ckb:زمانی شێوەیی |
||
خط ۶۲: | خط ۶۲: | ||
[[bg:Формален език (математика)]] |
[[bg:Формален език (математика)]] |
||
[[bs:Formalni jezik]] |
[[bs:Formalni jezik]] |
||
[[ckb:زمانی شێوەیی]] |
|||
[[cs:Formální jazyk]] |
[[cs:Formální jazyk]] |
||
[[da:Formelt sprog]] |
[[da:Formelt sprog]] |
نسخهٔ ۸ دسامبر ۲۰۰۹، ساعت ۱۵:۲۸
در ریاضیات، منطق و دانش رایانه، به زبانی که با فرمولهای دقیق ریاضیاتی و قابل پردازش برای ماشین تعریف شداند، زبانهای فُرمال یا زبانهای صوری گفته میشود.
به طور کلی در این رشتهها، زبان ها به دو دسته فرمال و طبیعی تقسیم بندی میشوند . زبان های فرمال زبان هایی هستند که توسط گرامر ها تولید میشوند یا ماشینی برای ارزبابی آنها وجود دارد .
تعاریف پایه
- نماد : کوچک ترین و بنیادی ترین عضو یک زبان است . برخی مواقع به نماد ها حرف هم گفته میشود . نماد ها را معمولاً با حروف لاتین کوچک مثل 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 [۱]