زبان صوری

از ویکی‌پدیا، دانشنامهٔ آزاد

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

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

تعاریف پایه

  • نماد: کوچک‌ترین و بنیادی‌ترین عضو یک زبان است. برخی مواقع به نمادها «حرف» هم گفته می‌شود. نمادها را معمولاً با حروف لاتین کوچک، مثل 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 [۱]