آتوماتا:
درعلوم نظریه رایانه، نظریهٔ اتوماتا (به انگلیسی: Automata theory) یا نظریهٔ ماشین‌ها عبارت است از بررسی ریاضی ماشین‌های محاسبه‌گر انتزاعی و توانایی‌های آنها برای حل مسایل. به این ماشین‌های انتزاعی اتوماتا گفته می شود. این نظریه بسیار نزدیک به نظریه زبانهای فرمال است. به طوری که اتوماتا اغلب توسط دستهٔ زبانهای رسمی قابل تشخیص دسته بندی می شوند. اتوماتا نقش اساسی در طراحی کامپایلر و تجزیه کردن (parsing) ایفا می کند. زبان‌هایی که توسط این ماشین‌ها بررسی می‌شوند زبانهای فرمال هستند.یک ماشین خودکار قرار است که بر روی تعدادی ورودی از دنباله یا رشته در مراحل زمانی گسسته اجرا شود. در هر مرحله از زمان، ماشین یک ورودی که از مجموعه‌ای از نمادها یا حرف‌ها برداشته شده‌است را، می‌گیرد که به آن الفبا (Alphabet) گفته می‌شود. یک ماشین حاوی مجموعهٔ متناهی از حالت‌هاست. در هر لحظه از اجرا بسته به نوع ماشین، می‌تواند در یکی یا چند تا از حالت‌هایش باشد. در هر مرحلهٔ زمانی، هنگامی که ماشین یک نماد را می‌خواند، بر اساس حالت فعلی و نماد خوانده شده به حالت بعدی پرش یا گذر می‌کند. این تابع روی حالت فعلی و نماد ورودی تابع گذار گفته می‌شود. ماشین تا زمانی که یک ورودی کامل خوانده شود ورودی را نماد به نماد در دنباله‌ای می‌خواند و از حالتی به حالت دیگر بر اساس تابع گذار، گذر می‌کند. زمانی که ورودی نهایی خوانده می‌شود، اصطلاحاً ماشین متوقف شده‌است و به این حالت، حالت نهایی می‌گویند. بر اساس حالت نهایی گفته می‌شود که ماشین یک ورودی را قبول یا رد کرده‌است. زیر مجموعه‌ای از حالت‌های ماشین وجود دارد که به عنوان مجموعهٔ حالت‌های مورد قبول تعریف می‌شود. اگر حالت نهایی یک حالت مورد قبول باشد ماشین ورودی را پذیرفته‌است. در غیر این صورت ورودی رد می‌شود. به مجموعه‌ای از ورودی‌ها که توسط ماشین پذیرفته می‌شود زبان قابل تشخیص ماشین می‌گویند.
به زبان راحت تر:
يک اتوماتا،يک مدل انتزاعي از يک کامپيوترديجيتال ميباشد. هراتوماتا ورودي را خوانده بدون تغييردادن فايل ورودي، فاي لورودي را ميخواند. فايل ورودي به قسمتهايي بنام سلول تقسيم ميشود.اتوماتا ممکن است داراي يک حافظه موقت نيزبراي ذخيره موقت داده ها باشد که اين حافظه نيزازسلول تشکي لشده است.اين حافظه برخلاف فاي لورودي قاب لتغييرميباشد.
درنهايت اتوماتا داراي يک واحد کنترل نيزمي باشد با اعمال پردازشهاي مورد نظراتوماتاي ما خروجي را درفايل خروجي توليد مي نمايد در زير ميتوانيد شکل انتزاعي مورد نظر رامشاهده فرماييد.
http://www.250kb.com/u/110414/j/13296e3c.jpg
درمرحله اول اتوماتا ورودي راScan ميکند درهرمرحله از زمان اتوماتاي مادر يک حالت دروني ميباشد. حالت دروني بعدي باتوجه به حالت بعدي وتابع انتقال اعمال ميشود. تابعانتقال باتوجه به حالت فعلي و ورودي مادر سلول جاري واطلاعات خوانده شده در نوار حافظه تعيين مي شود. درحين انتقال به حالت بعدي ممکن است خروجي نيز دريک سلول درج شود.
ممکن است وقتي ما به يک حالت بعد ميرويم دو استراتژيک را اتخاذ نماييم حالت بعدي آيا يک حالت قطعي ميباشد يابين چند حالت بعدي يکي را انتخاب نماييم که اين اتوماتا به اتوماتاي غير قطعي معروف ميباشد.