در این بخش شما را برای چیزی آماده می‌کنیم که قرار است در آینده به آن بپردازیم. در ابتدا برخی از ایده‌های اصلی را از ریاضیات محدود بررسی کرده و نماد استفاده‌شده در متن را مشخص می‌نماییم. بویژه، تکنیک‌های اثبات، به ویژه اثبات توسط استقرا و اثبات توسط برهان خلف هستند.
بخش بعدی به شما اولین نگاه را به ایده‌هایی ارائه می‌دهد که در هسته این آموزش ها هستند: automata، زبان‌ها، گرامر، تعاریف و روابطشان. در آموزش های بعدی، ما این ایده‌ها را توسعه خواهیم داد و تعدادی از انواع مختلف گرامرها را مطالعه خواهیم کرد.
در بخش بعد از آن، ما با برخی مثال‌های ساده از نقش این مفاهیم در علوم کامپیوتر، به خصوص در زبان‌های برنامه‌نویسی، طراحی دیجیتال، و پردازش متن مواجه می‌شویم. ما این مساله را در اینجا مورد بررسی قرار نمی‌دهیم، چرا که شما با استفاده از این مفاهیم در تعدادی از دوره‌های دیگر CS (علوم کامپیوتر) برخورد خواهید کرد.
موضوع اصلی این کتاب، نظریه محاسبات، شامل چندین موضوع است: نظریه automata، زبان‌های رسمی و گرامر، computability یا محاسبه پذیری، و پیچیدگی. این ها با هم پایه نظری علم کامپیوتر را تشکیل می‌دهد. ما در مورد automata، گرامر، و computability به عنوان مطالعه آنچه که می توان توسط کامپیوترها در اصل انجام داد به ندرت فکر کنیم، در حالی که پیچیدگی تعیین می‌کند که چه چیزی می‌تواند در عمل انجام شود. در این آموزش ها ما تقریبا به طور کامل به اولین مورد از این نگرانی‌ها تمرکز می‌کنیم. ما آتوماتاهای مختلف را مطالعه خواهیم کرد، چگونگی ارتباط آن‌ها با زبان‌ها و گرامر را بررسی کرده، و تحقیق می‌کنیم که چه چیزی می‌تواند و نمی‌تواند توسط کامپیوترهای دیجیتال انجام شود. اگرچه این نظریه کاربردهای زیادی دارد اما ذاتا انتزاعی و ریاضی است.
علوم کامپیوتر یک رشته عملی است. آن‌هایی که در آن کار می‌کنند اغلب ترجیح مشخصی برای مشکلات مفید و ملموس در مورد گمانه‌زنی‌های نظری دارند. این قطعا در مورد دانش آموزانی که عمدتا با کاربردهای دشوار از دنیای واقعی سروکار دارند، صادق است. سوالات نظری تنها در صورتی به آن‌ها علاقمند هستند که به یافتن راه‌حل‌های خوب کمک کنند. این نگرش مناسب است چون بدون برنامه‌های کاربردی علاقه چندانی به کامپیوترها وجود نخواهد داشت. اما با توجه به این جهت گیری عملی، یکی ممکن است بپرسد چرا باید تئوری را مطالعه کرد؟
اولین پاسخ این است که تئوری مفاهیم و اصولی را ارایه می‌دهد که به ما کمک می‌کنند ماهیت عمومی نظم را درک کنیم. زمینه علوم کامپیوتر شامل طیف وسیعی از موضوعات خاص، از طراحی ماشین تا برنامه‌نویسی است. استفاده از کامپیوترها در دنیای واقعی شامل یک مجموعه از جزئیات خاص است که باید برای یک کاربرد موفق یاد گرفته شوند. این باعث می‌شود که علوم کامپیوتر یک رشته بسیار متنوع و گسترده باشد. اما با وجود این تنوع، اصول اساسی مشترکی وجود دارد. برای مطالعه این اصول اولیه، ما مدل‌های انتزاعی از کامپیوترها و محاسبات می‌سازیم.
این مدل‌ها ویژگی‌های مهمی را در خود دارند که در هر دو سخت‌افزار و هم نرم‌افزار مشترک هستند و برای بسیاری از سازه‌های خاص و پیچیده که ما هنگام کار با کامپیوترها مواجه هستیم، ضروری هستند. حتی زمانی که چنین مدل‌هایی، بسیار ساده باشند تا بلافاصله در موقعیت‌های دنیای واقعی قابل‌اجرا باشند، دیدگاه‌هایی که از مطالعه آن‌ها بهره می‌بریم، پایه‌ای را فراهم می‌کنند که توسعه خاص بر اساس آن استوار است. البته این رویکرد منحصر به علم کامپیوتر نیست. ساخت مدل‌ها یکی از موارد ضروری هر رشته علمی است، و سودمندی یک رشته، اغلب وابسته به وجود ساده، در عین حال قدرتمند، تئوری‌ها و قوانین است.
دوم اینکه شاید چندان واضح نباشد، پاسخ این است که ایده‌هایی که در مورد آن بحث خواهیم کرد، کاربردهای آنی و مهمی خواهند داشت. زمینه‌های طراحی دیجیتالی، زبان‌های برنامه‌نویسی، و کامپایلرها نمونه‌های بارز هستند، اما بسیاری دیگر نیز وجود دارند. مفاهیمی که ما در اینجا مطالعه می‌کنیم مانند رشته‌ای از علوم رایانه، از سیستم‌های عامل برای شناسایی الگو، اجرا می‌شوند.
سومین پاسخ این است که ما امیدواریم که خواننده را قانع کنیم. موضوع مورد بحث، مهیج و سرگرم‌کننده است. این کار بسیاری چالش برانگیز و معما دارد – مانند مشکلاتی که می‌توانند به برخی از شب‌های بی‌خوابی منتهی شوند. این مساله حل مساله در جوهر خالص آن است.
مقداد علی بخشی هستم. موسیقی دان، برنامه نویس، متخصص هوش مصنوعی، علم داده، متخصص بلاکچین و توسعه دهنده ربات های هوشمند.
دانش آموخته مقطع ارشد و دکتری دانشکده فنی دانشگاه تهران هستم. با سابقه تدریس درس برنامه نویسی در دانشگاه (پردیس بین الملل کیش دانشگاه تهران)