نظریه زبان‌ها

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

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

تعاریف پایه

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

• الفبا : یک مجموعه متناهی از نمادها که در یک زبان تعریف شده اند . الفبای زبان توسط Σ نشان داده می شود .

• رشته : دنباله ای از نماد های یک مجموعه الفباست که با عمل الحاق به هم پیوسته اند .

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

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

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

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

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

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

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

• زبان‌های منظم
• زبان‌های مستقل از متن
• زبان‌های حساس به متن
• زبان‌های بدون محدودیت

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

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

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

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

منابع

An Introduction to Formal Languages and Automata, Peter Linz