نظریه زبان‌ها: تفاوت میان نسخه‌ها

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

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

* [[نماد]]: کوچک‌ترین و بنیادی‌ترین عضو یک زبان است. برخی مواقع به نمادها «حرف» هم گفته می‌شود. نمادها را معمولاً با حروف لاتین کوچککوچک، مثل aa‏، b و…و…، نشان می‌دهند.

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

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

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

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

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

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

رشته‌ای به طولبه طول صفر را با λ یا ε نشان می‌دهند. و آن را [[رشته تهی|رشتهٔ تهی]] می‌نامند.

* [[زبان حساس به متن|زبان‌های حساسحسّاس به متن]]

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

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

[[الحاق (نظریه ماشین‌ها)|عملگرعمل‌گر الحاق]] که روی رشته‌ها تعریف شده‌است، روی زبان‌ها نیز قابل تعریفقابل‌تعریف است.

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

یک زبان صوری <math>L \!</math> بر روی یک الفبای <math>\Sigma \!</math> عبارت است از یک زیرمجموعه از <math>\Sigma^{*} \!</math>.

== پانوشته‌هاپانوشت‌ها ==

• An Introduction to Formal Languages and Automata، Peter Linz