نظریه زبانها: تفاوت میان نسخهها
Kirjoitusvirhe korjattu برچسبها: نیازمند بازبینی ویرایش همراه ویرایش از برنامهٔ همراه |
جز ربات:افزودن الگو ناوباکس {{منطق}}+املا (۹.۱) |
||
خط ۴: | خط ۴: | ||
== تعاریف پایه == |
== تعاریف پایه == |
||
* [[نماد]] : کوچکترین و بنیادیترین عضو یک زبان است . برخی مواقع به نمادها حرف هم گفته میشود . نمادها را معمولاً با حروف لاتین کوچک مثل a ، b و ... نشان میدهند . |
* [[نماد]] : کوچکترین و بنیادیترین عضو یک زبان است . برخی مواقع به نمادها حرف هم گفته میشود . نمادها را معمولاً با حروف لاتین کوچک مثل a ، b و ... نشان میدهند . |
||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
رشته ممکن است متناهی یا غیر متناهی باشد . طول یک رشته برابر است با تعداد نمادهایی که رشته را تشکیل میدهند . طول رشته را با قدر مطلق آن نمایش میدهند . مثلاً : |
رشته ممکن است متناهی یا غیر متناهی باشد . طول یک رشته برابر است با تعداد نمادهایی که رشته را تشکیل میدهند . طول رشته را با قدر مطلق آن نمایش میدهند . مثلاً : |
||
اگر w=aabbbbc آنگاه طول رشته ( |w| ) برابر است با هفت . زیرا این رشته با هفت نماد ساخته شده است . |
اگر w=aabbbbc آنگاه طول رشته ( |w| ) برابر است با هفت . زیرا این رشته با هفت نماد ساخته شده است . |
||
* زبان : مجموعهای از رشتهها است . این مجموعه میتواند متناهی، نامتناهی شمارا یا نامتناهی ناشمارا باشد . |
* زبان : مجموعهای از رشتهها است . این مجموعه میتواند متناهی، نامتناهی شمارا یا نامتناهی ناشمارا باشد . |
||
خط ۲۴: | خط ۲۰: | ||
زبانهای فرمال به چهار دسته تقسیم میشوند : |
زبانهای فرمال به چهار دسته تقسیم میشوند : |
||
* [[زبانهای منظم]] |
* [[زبانهای منظم]] |
||
* [[زبانهای مستقل از متن]] |
* [[زبانهای مستقل از متن]] |
||
خط ۴۴: | خط ۳۹: | ||
== پانوشتهها == |
== پانوشتهها == |
||
<References |
<References/> |
||
== منابع == |
== منابع == |
||
{{پانویس}} |
|||
An Introduction to Formal Languages and Automata، Peter Linz |
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 [http://www.amazon.com/Languages-Machines-Introduction-Computer-Science/dp/0321322215] |
* 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 [http://www.amazon.com/Languages-Machines-Introduction-Computer-Science/dp/0321322215] |
||
{{پایان چپچین}} |
{{پایان چپچین}} |
||
{{منطق}} |
|||
[[رده:زبانهای صوری]] |
[[رده:زبانهای صوری]] |
||
[[رده:علوم نظری رایانه]] |
[[رده:علوم نظری رایانه]] |
نسخهٔ ۷ دسامبر ۲۰۱۴، ساعت ۰۹:۳۶
در ریاضیات، منطق و دانش رایانه، به زبانی که با فرمولهای دقیق ریاضیاتی و قابل پردازش برای ماشین تعریف شداند، زبانهای فُرمال یا زبانهای صوری گفته میشود.
به طور کلی در این رشتهها، زبانها به دو دسته فرمال و طبیعی تقسیم بندی میشوند . زبانهای فرمال زبان هایی هستند که توسط گرامرها تولید میشوند یا ماشینی برای ارزیابی آنها وجود دارد .
تعاریف پایه
- نماد : کوچکترین و بنیادیترین عضو یک زبان است . برخی مواقع به نمادها حرف هم گفته میشود . نمادها را معمولاً با حروف لاتین کوچک مثل 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 [۱]