در علوم نظری رایانه، نظریهٔ اتوماتا (به انگلیسی: Automata theory) یا نظریهٔ ماشین‌ها عبارت است از بررسی ریاضی ماشینهای محاسبه‌گر انتزاعی و توانایی‌های آنها برای حل مسایل. به این ماشینهای انتزاعی اتوماتا گفته می‌شود. این نظریه بسیار نزدیک به نظریهٔ زبان صوری است. به طوری که اتوماتا اغلب توسط دستهٔ زبانهای رسمی قابل تشخیص دسته‌بندی می‌شوند. اتوماتا نقش اساسی در طراحی کامپایلر و تجزیه کردن (parsing) ایفا می‌کند. زبان‌هایی که توسط این ماشین‌ها بررسی می‌شوند زبانهای فرمال هستند.
توضیحات پایه
یک ماشین، یک مدل ریاضی از ماشین حالات متناهی (FSM) است. یک ماشین شامل مجموعه‌ای متناهی از حالات است که بر اساس ورودی و تابع گذار خود (که میتواند به صورت جدول باشد)، از یک حالت به حالت دیگر، تغییر وضعیت می‌دهد. این تابع انتقال به ماشین خودکار می‌گوید که به کدام حالت بعدی با توجه به حالت فعلی و نماد داده شده، برود.
به صورت کلی، یک ماشین شامل مجموعه‌ای متناهی یا شماری از حالات مختلف است.
فهرست مطالب:
مفاهیم نمادگذاری و مفهوم تابع
نظریه مجموعه ها
مفهوم استقرا ریاضی
گراف و انواع آن
مفاهیم رشته و زبان
مشخصات زبان ها
مجموعه های با قاعده
گرامرها و زبانهای مستقل از متن
اشتقاق و درخت آن
گرامرهای قاعده
اشتقتاق چپ و ابهام
گراف یک گرامر
پارسرها
فرمهای نرمال
حذف قوانین لامبدا
حذف قوانین زنجیره ای
حذف نرمال شومسکی و گریپاش
آتاماتای قطعی
دیاگرام حالت
آتاماتی غیرقطعی
آتاماتی متناهی
گراف عبارت
زبان بی قاعده
آتاماتای pushdown
انواع PDA
آتاماتی دوپشته ای
بهینه سازی DFA
ماشین تورینگ
انواع پذیرش
ماشینهای چند شیاره
ماشینهای تورینگ غیرقطعی
گرامرهای بدون محدودیت
گرامرهای وابسته به متن
آتاماتای خطی محدود
طبقه بندی شومسکی
تمامی این مطالب با مثالهای مختلف در 10 فصل گردآوری شده است.
پاورپوینت آموزش کامل نظریه زبان ها و ماشین ها (نظریه اوتوماتا) در 225 اسلاید
