زبان صوری

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

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

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

تعاریف پایه[ویرایش]

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

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

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

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

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

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

دسته‌بندی زبان‌های فرمال[ویرایش]

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

عملگرهای روی زبان‌های فرمال[ویرایش]

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

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

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

تعریف[ویرایش]

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

پانوشته‌ها[ویرایش]


منابع[ویرایش]

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 [۱]