نویسنده : Thomas A.Sudkamp

مترجم: مهندس سید حجت الله جلیلی

انتشارات: پژوهشهای فرهنگی(۱۳۸۰)

ناشر : جزوه

 توضیحات

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

به صورت کلی، یک ماشین شامل مجموعه‌ای متناهی یا شماری از حالات مختلف است.

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

فهرست

فصل اول: ریاضیات مقدماتی

مفاهیم نمادگذاری و مفهوم تابع

نظریه مجموعه ها

مفهوم استقراء ریاضی

گراف و انواع آن

فصل دوم: زبان ها

مفاهیم رشته و زبان

مشخصات زبان ها

مجموعه های با قاعده

فصل سوم: گرامرهای مستقل از متن

گرامرها و زبان های مستقل از متن

اشتقاق و درخت آن

گرامرهای قاعده

فصل چهارم: مقدمه ای بر پارسر ها

اشتقاق چپ و ابهام

گراف یک گرامر

پارسر ها

فصل پنجم: فرم های نرمال

فرم های نرمال

حذف قوانین لامبدا

حذف قوانین زنجیره ای

فرم نرمال شومسکی وگریباش

فصل ششم: آتاماتای متناهی

آتاماتای قطعی

دیاگرام حالت

آتاماتای غیر قطعی

فصل هفتم : زبانها و مجموعه های با قاعده

آتاماتای متناهی و مجموعه های با قاعده

گراف عبارت

زبان  بی قاعده

فصل هشتم: آتاماتای Pushdown

آتاماتای Pushdown

انواع PDA

آتاماتای دو پشته ای

بهینه سازی DFA

فصل نهم:ماشینهای تورینگ

ماشین تورینگ

انواع پذیرش

ماشین های چند شیاره

ماشین های تورینگ غیر قطعی

فصل دهم:طبقه بندی شومسکی

گرامرهای بدون محدودیت

گرامرهای وابسته به متن

آتاماتای خطی محدود

طبقه بندی شومسکی