زبان صوری

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

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

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

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

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

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

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

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

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

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

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

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

• نظریه اتوماتا
• ماشین‌های تورینگ

An Introduction to Formal Languages and Automata، Peter Linz