کتاب آموزش نظریه زبان‌ها و ماشین

کتاب آموزش نظریه زبان‌ها و ماشین

در خدمت شما هستیم با دانلود رایگان کتاب آموزش نظریه زبان‌ها و ماشین از وب سایت آموزش برنامه نویسی سورس باران. این کتاب پیش نیاز درس طراحی کامپایلر برای دانشجویان نرم افزار و برنامه نویسان است. با یادگیری زبان‌ها و گرامرها می‌توانید نحوه کار کامپایلر و همچنین طراحی زبان‌ های برنامه سازی را متوجه شوید. یادگیری این درس بدون مدرس کار ساده‌ای نمی‌باشد و در این آموزش تجربه حداقل پانزده سال تدریس نویسنده در اختیار شما گذاشته می‌شود.

این کتاب نوشته فرشید شیرافکن و 260 صفحه ارائه شده که در آن با زبان، گرامر و ماشین آشنا می شوید.

کتاب آموزش نظریه زبان‌ها و ماشین

• فصل ۱: عبارت منظم – زبان منظم
• فصل ۲: گرامر – گرامر منظم
• فصل ۳: اتوماتای متناهی (DFA, NFA)
• فصل ۴: زبان و گرامر مستقل از متن
• فصل ۵: ابهام – ساده سازی گرامر – فرم‌های نرمال
• فصل ۶: اتوماتای پشته‌ای (DPDA, NPDA)
• فصل ۷: ماشین‌های تورینگ (TM)
• فصل ۸: زبان‌های بازگشتی – گرامر بدون محدویت و حساس به متن

حتما مشاهده کنید : آرشیو کامل کتاب های آموزش برنامه نویسی سورس باران

نظریه زبان‌ها و ماشین چیست؟

شاید بپرسید نظریه زبانها کجا کاربرد دارد؟ اصلا به چه درد میخورد؟ جواب سوال را به این شکل بگوییم، الان در این صفحه شما دارید با نظریه زبان‌ها و ماشین‌ ها آشنا می‌شوید. همه این زبان‌ها یا کامپایلر دارد یا مفسر و بعضی هم هردو را دارا هستند.

این کامپایلر و مفسر وظیفه‌شان این هست که دستورایی که شما برای کامپیوتر به زبان محاوره دارید داخلش مینویسید، به زبان قابل فهم ماشین تبدیل میکند (یعنی همون صفر و یک). فرض کنید در آینده شما می‌خواهید یک زبان برنامه‌ نویسی طراحی و ابداع کنید خب قبل از همه چیز باید کامپایلر زبان خودتان را بنویسید و به ماشین بگویید در این زبان هر دستور به چه شکلی هست و چه برداشتی باید از این دستور انجام شود.  برای طراحی یک کامپایلر شما باید با نظریه زبان‌ها و ماشین‌ها آشنا باشید و بلکه هم بیشتر از آشنایی باید بدانید.

در علوم نظریه رایانه‌ها، نظریه‌ی اتوماتا به انگلیسی Automata theory یا نظریه‌ی ماشین‌ها عبارت است از بررسی ریاضی ماشین‌های محاسبه‌گر انتزاعی و توانایی‌های آن‌ها برای حل مسایل. به این ماشین‌های انتزاعی اتوماتا گفته می‌شود. این نظریه بسیار نزدیک به نظریه زبان صوری است. به‌طوری‌که اتوماتا اغلب توسط دسته? زبان‌های رسمی قابل تشخیص دسته‌بندی می‌شوند. اتوماتا نقش اساسی در طراحی کامپایلر و تجزیه کردن (parsing) ایفا می‌کند. زبان‌هایی که توسط این ماشین‌ها بررسی می‌شوند زبان های فرمال هستند.

یک ماشین، یک مدل ریاضی از ماشین حالات متناهی (FSM) است. یک ماشین شامل مجموعه‌ای متناهی از حالات است که بر اساس ورودی و تابع گذار خود (که می‌تواند به صورت جدول باشد)، از یک حالت به حالت دیگر، تغییر وضعیت می‌دهد. این تابع انتقال به ماشین خودکار می‌گوید که به کدام حالت بعدی با توجه به حالت فعلی و نماد داده شده، برود. به صورت کلی، یک ماشین شامل مجموعه‌ای متناهی یا شماری از حالات مختلف است.

یک ماشین خودکار قرار است که بر روی تعدادی ورودی از دنباله یا رشته در مراحل زمانی گسسته اجرا شود. در هر مرحله از زمان، ماشین یک ورودی که از مجموعه‌ای از نمادها یا حرف‌ها برداشته شده‌است را، می‌گیرد که به آن الفبا (Alphabet) گفته می‌شود. یک ماشین حاوی مجموعه‌ی متناهی از حالت هاست. در هر لحظه از اجرا بسته به نوع ماشین، می‌تواند در یکی یا چند تا از حالت‌هایش باشد. در هر مرحله‌ی زمانی، هنگامی که ماشین یک نماد را می‌خواند، بر اساس حالت فعلی و نماد خوانده شده به حالت بعدی پرش یا گذر می‌کند.

این تابع روی حالت فعلی و نماد ورودی تابع‌گذار گفته می‌شود. ماشین تا زمانی که یک ورودی کامل خوانده شود ورودی را نماد به نماد در دنباله‌ای می‌خواند و از حالتی به حالت دیگر بر اساس تابع گذار، گذر می‌کند. زمانی که ورودی نهایی خوانده می‌شود، اصطلاحاً ماشین متوقف شده‌است و به این حالت، حالت نهایی می‌گویند. بر اساس حالت نهایی گفته می‌شود که ماشین یک ورودی را قبول یا رد کرده‌است. زیر مجموعه‌ای از حالت‌های ماشین وجود دارد که به عنوان مجموعه‌ی حالت‌های مورد قبول تعریف می‌شود. اگر حالت نهایی یک حالت مورد قبول باشد ماشین ورودی را پذیرفته ‌است. در غیر این صورت ورودی رد می‌شود. به مجموعه‌ای از ورودی‌ها که توسط ماشین پذیرفته می‌شود زبان قابل تشخیص ماشین می‌گویند.

راستی! برای دریافت مطالب جدید در کانال تلگرام یا پیج اینستاگرام سورس باران عضو شوید.