نظریه زبان‌ها: تفاوت میان نسخه‌ها
جز ربات: اصلاح نیم فاصله مجازی |
جز ربات: اصلاح نیم فاصله مجازی |
||
| خط ۱: | خط ۱: | ||
در [[ریاضیات]]، [[منطق]] و دانش [[رایانه]]، به زبانی که با فرمول‌های دقیق ریاضیاتی و قابل پردازش برای ماشین تعریف شد‌اند، '''زبان‌های فُرمال''' یا '''زبان‌های صوری''' گفته می‌شود. |
در [[ریاضیات]]، [[منطق]] و دانش [[رایانه]]، به زبانی که با فرمول‌های دقیق ریاضیاتی و قابل پردازش برای ماشین تعریف شد‌اند، '''زبان‌های فُرمال''' یا '''زبان‌های صوری''' گفته می‌شود. |
||
به طور کلی در این رشته‌ها، زبان ها به دو دسته فرمال و طبیعی تقسیم بندی |
به طور کلی در این رشته‌ها، زبان ها به دو دسته فرمال و طبیعی تقسیم بندی می‌شوند . زبان های فرمال زبان هایی هستند که توسط گرامر ها تولید می‌شوند یا ماشینی برای ارزبابی آنها وجود دارد . |
||
| خط ۷: | خط ۷: | ||
* [[نماد]] : کوچک ترین و بنیادی ترین عضو یک زبان است . برخی مواقع به نماد ها حرف هم گفته می‌شود . نماد ها را معمولاً با حروف لاتین کوچک مثل a ، b و ... نشان |
* [[نماد]] : کوچک ترین و بنیادی ترین عضو یک زبان است . برخی مواقع به نماد ها حرف هم گفته می‌شود . نماد ها را معمولاً با حروف لاتین کوچک مثل a ، b و ... نشان می‌دهند . |
||
* الفبا : یک مجموعه متناهی از نمادها که در یک زبان تعریف شده اند . الفبای زبان توسط Σ نشان داده می‌شود . |
* الفبا : یک مجموعه متناهی از نمادها که در یک زبان تعریف شده اند . الفبای زبان توسط Σ نشان داده می‌شود . |
||
| خط ۱۳: | خط ۱۳: | ||
* رشته : دنباله ای از نماد های یک مجموعه الفباست که با عمل الحاق به هم پیوسته اند . |
* رشته : دنباله ای از نماد های یک مجموعه الفباست که با عمل الحاق به هم پیوسته اند . |
||
رشته ممکن است متناهی یا غیر متناهی باشد . طول یک رشته برابر است با تعداد نمادهایی که رشته را تشکیل |
رشته ممکن است متناهی یا غیر متناهی باشد . طول یک رشته برابر است با تعداد نمادهایی که رشته را تشکیل می‌دهند . طول رشته را با قدر مطلق آن نمایش می‌دهند . مثلاً : |
||
اگر w=aabbbbc آنگاه طول رشته ( |w| ) برابر است با هفت . زیرا این رشته با هفت نماد ساخته شده است . |
اگر w=aabbbbc آنگاه طول رشته ( |w| ) برابر است با هفت . زیرا این رشته با هفت نماد ساخته شده است . |
||
| خط ۱۹: | خط ۱۹: | ||
* زبان : مجموعه ای از رشته ها است . این مجموعه می‌تواند متناهی ، نامتناهی شمارا یا نامتناهی ناشمارا باشد . |
* زبان : مجموعه ای از رشته ها است . این مجموعه می‌تواند متناهی ، نامتناهی شمارا یا نامتناهی ناشمارا باشد . |
||
زبان بدون رشته را با Ø نشان |
زبان بدون رشته را با Ø نشان می‌دهند . |
||
رشته ای به طول صفر را با λ یا ε نشان |
رشته ای به طول صفر را با λ یا ε نشان می‌دهند . آن را [[رشته تهی]] می نامند . |
||
== دسته‌بندی زبان‌های فرمال == |
== دسته‌بندی زبان‌های فرمال == |
||
زبان های فرمال به چهار دسته تقسیم |
زبان های فرمال به چهار دسته تقسیم می‌شوند : |
||
* [[زبان‌های منظم]] |
* [[زبان‌های منظم]] |
||
نسخهٔ ۲۰ ژوئن ۲۰۰۹، ساعت ۲۳:۱۰
در ریاضیات، منطق و دانش رایانه، به زبانی که با فرمول‌های دقیق ریاضیاتی و قابل پردازش برای ماشین تعریف شد‌اند، زبان‌های فُرمال یا زبان‌های صوری گفته می‌شود.
به طور کلی در این رشته‌ها، زبان ها به دو دسته فرمال و طبیعی تقسیم بندی می‌شوند . زبان های فرمال زبان هایی هستند که توسط گرامر ها تولید می‌شوند یا ماشینی برای ارزبابی آنها وجود دارد .
تعاریف پایه
- نماد : کوچک ترین و بنیادی ترین عضو یک زبان است . برخی مواقع به نماد ها حرف هم گفته می‌شود . نماد ها را معمولاً با حروف لاتین کوچک مثل 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 [۱]