تعاریف اولیه نظریه زبان‌ها و ماشین‌ها (زبان، کلمه، الفبا)

نظریه زبان‌ها و ماشین‌ها شاخه‌ای از علوم کامپیوتر است که عموما در دوره تابستانه المپیاد کامپیوتر با نام اتوماتا تدریس می‌شود. در این نظریه به مطالعه زبان‌های قراردادی (به معنای زبان‌هایی که خودمان تعریف می‌کنیم.) یا همان زبان‌های فرمال (Formal Language) و همچنین ماشین‌های محاسباتی (Automata) می‌پردازیم. این نظریه مبنای تئوری و ریاضی کامپایلرهای برنامه‌نویسی و به طور کلی محاسبات کامپیوتری می‌باشد.

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

به عنوان مثال، الفبای انگلیسی شامل حروف بزرگ و کوچک، اعداد و علائم نگارشی است. الفبای زبان انگلیسی فقط با در نظر گرفتن حروف کوچک و اعداد به صورت زیر می‌باشد: $$\Sigma=\{a, b, c ..., z, 0, 1, 2, ..., 9\}$$ دقت کنید که الفبا حتما باید متناهی باشد.

• رشته متناهی از نمادهای انتخاب شده از یک الفبا است.
• طول یک کلمه برابر با تعداد نمادهای تشکیل‌دهنده آن است.
• همچنین کلمه با طول صفر نیز تعریف می‌شود و با نماد $\epsilon$ نمایش می‌دهند.

به عنوان مثال، «hello» یک کلمه در الفبای انگلیسی است.

• مجموعه‌ای از کلمات ساخته شده از یک الفبا است.
• زبان‌ها می‌توانند متناهی یا نامتناهی باشند.

به عنوان مثال، زبان اعداد طبیعی یک زبان نامتناهی است، زیرا تعداد اعداد طبیعی نامتناهی هستند. $$\Sigma=\{0, 1, 2, ..., 9\}$$ $$L=\{1, 2, 3, 4, 5, ...\}$$ البته دقت کنید طول هر رشته از این زبان (هر کدام از اعداد طبیعی را به صورت رشته در نظر بگیرید.) متناهی می‌باشد. به طور مثال طول عدد ۱۳۸۰۰۷۲۵ اگر به صورت رشته در نظر گرفته‌شود، برابر با ۸ است.