نظریه اتوماتا
در علوم نظری رایانه، نظریهٔ اتوماتا یا نظریهٔ ماشین‌ها عبارت است از بررسی ریاضی ماشین‌های محاسبه‌گر انتزاعی و توانایی‌های آن‌ها برای حل مسایل. به این ماشین‌های انتزاعی اتوماتا گفته می‌شود. این نظریه بسیار نزدیک به نظریهٔ زبان صوری است. به‌طوری‌که اتوماتا اغلب توسط دستهٔ زبان‌های رسمی قابل تشخیص دسته‌بندی می‌شوند. اتوماتا نقش اساسی در طراحی کامپایلر و تجزیه کردن (parsing) ایفا می‌کند. زبان‌هایی که توسط این ماشین‌ها بررسی می‌شوند زبان‌های فرمال هستند.
یک ماشین، یک مدل ریاضی از ماشین حالات متناهی (FSM) است. یک ماشین شامل مجموعه‌ای متناهی از حالات است که بر اساس ورودی و تابع گذار خود (که می‌تواند به صورت جدول باشد)، از یک حالت به حالت دیگر، تغییر وضعیت می‌دهد. این تابع انتقال به ماشین خودکار می‌گوید که به کدام حالت بعدی با توجه به حالت فعلی و نماد داده شده، برود.
به صورت کلی، یک ماشین شامل مجموعه‌ای متناهی یا شماری از حالات مختلف است.
یک ماشین خودکار قرار است که بر روی تعدادی ورودی از دنباله یا رشته در مراحل زمانی گسسته اجرا شود. در هر مرحله از زمان، ماشین یک ورودی که از مجموعه‌ای از نمادها یا حرف‌ها برداشته شده‌است را، می‌گیرد که به آن الفبا (Alphabet) گفته می‌شود. یک ماشین حاوی مجموعهٔ متناهی از حالت هاست. در هر لحظه از اجرا بسته به نوع ماشین، می‌تواند در یکی یا چند تا از حالت‌هایش باشد. در هر مرحلهٔ زمانی، هنگامی که ماشین یک نماد را می‌خواند، بر اساس حالت فعلی و نماد خوانده شده به حالت بعدی پرش یا گذر می‌کند. این تابع روی حالت فعلی و نماد ورودی تابع‌گذار گفته می‌شود. ماشین تا زمانی که یک ورودی کامل خوانده شود ورودی را نماد به نماد در دنباله‌ای می‌خواند و از حالتی به حالت دیگر بر اساس تابع گذار، گذر می‌کند. زمانی که ورودی نهایی خوانده می‌شود، اصطلاحاً ماشین متوقف شده‌است و به این حالت، حالت نهایی می‌گویند. بر اساس حالت نهایی گفته می‌شود که ماشین یک ورودی را قبول یا رد کرده‌است. زیر مجموعه‌ای از حالت‌های ماشین وجود دارد که به عنوان مجموعهٔ حالت‌های مورد قبول تعریف می‌شود. اگر حالت نهایی یک حالت مورد قبول باشد ماشین ورودی را پذیرفته‌است. در غیر این صورت ورودی رد می‌شود. به مجموعه‌ای از ورودی‌ها که توسط ماشین پذیرفته می‌شود زبان قابل تشخیص ماشین می‌گویند.
همچنین به هر نماد الفبا یک حرف گفته می‌شود. به عنوان مثال، الفبای لاتین {a,b،c... ,z}=∑ و الفبای باینری {۰و۱}=∑ مثال‌هایی از الفبا هستند که بیشترین کاربرد را برای ما دارند. طول رشته با علامت |w| نمایش داده می‌شود و به تعداد نمادهای موجود در رشته گفته می‌شود. رشتهٔ تهی با نماد ε یا ℷ نمایش داده می‌شود و طول آن برابر صفر در نظر گرفته می‌شود. به عنوان مثال اگر w=abcc آنگاه: ۴=|w|
۵ تایی formula_1 نمایندهٔ یک ماشین خودکار است که در آن: با داشتن حرف ورودی formula_7 که formula_8 می‌توان تابع‌گذار را به صورت formula_9 نوشت؛ که این کار با استفاده از ترفند سادهٔ مالش صورت می‌گیرد. (ترفند مالش عبارت است از نوشتن formula_10 به ازای همهٔ formula_11). با این روش، تابع‌گذار به فرم ساده‌تری تبدیل می‌شود. ترکیب تابع تکرار شده یک مونوئید را تشکیل می‌دهد. برای توابع گذار، این مونوئید تحت نام مونوئید گذار یا در بعضی مواقع "نیم گروه دگرسازی" شناخته می‌شود.
با داشتن یک جفت از حروف formula_12 تابع جدید formula_13 به صورت formula_14 تعریف می‌شود که formula_15 نشان دهندهٔ ترکیب توابع است. طبیعتاً، این فرایند می‌تواند به‌طور بازگشتی ادامه یابد و بنابراین یک تعریف بازگشتی از تابع formula_16 داریم که برای تمام کلمات formula_17 تعریف شده‌است و به شرح زیر است.
این ساختار می‌تواند معکوس هم بشود، با داشتن formula_13، می‌توان دوباره formula_20 را ساخت و بنابراین، این دو توصیف هم ارزند.
سه تایی formula_21 تحت نام ماشین نیمه خودکار شناخته می‌شود. ماشین نیمه خودکار همان ماشین خودکار است با این تفاوت که وضعیت شروع و مجموعهٔ وضعیت‌های قبول آن نادیده گرفته شده‌اند. مفهوم‌های افزودهٔ وضعیت اولیه و وضعیت قبول باعث می‌شوند تا توانائی ماشین خودکار بیش از توانائی ماشین نیمه خودکار باشد، بدین شرح که ماشین نیمه خودکار نمی‌تواند یک زبان صوری را شناسائی کند. زبان formula_22 که توسط ماشین خودکار کران‌دار پذیرفته شده‌است، این گونه تعریف می‌شود:
زبان پذیرفته شدهٔ ماشین خودکار (یعنی formula_22) مجموعه‌ای از کلمات formula_25 است که با الفبای formula_26 ساخته شده‌اند و وقتی به عنوان ورودی به ماشین خودکار داده می‌شوند، نهایتاً یکی از وضعیت‌های formula_5 را نتیجه می‌دهند. زبان‌هایی را که توسط ماشین خودکار پذیرفته شده‌اند، زبان‌های قابل تشخیص می‌نامند.
وقتی مجموعهٔ وضعیت‌های "Q" کران‌دار است، ماشین خودکار به عنوان ماشین خودکار کران‌دار شناخته می‌شود و مجموعهٔ همهٔ زبان‌های قابل تشخیص آن را، زبان‌های باقاعده می‌نامیم. در واقع یک هم‌ارزی قوی وجود دارد: به ازای هر زبان باقاعده یک ماشین خودکار وضعیت محدود وجود دارد.
در زیر، سه نوع از ماشین‌های خودکار کران‌دار ذکر شده‌است.
با این وجود می‌توان نشان داد که تمام این ماشین‌ها، می‌توانند زبان‌های مشابهی را بپذیرند.
خانوادهٔ زبان‌هایی که با ماشین‌های توصیف شده در بالا پذیرفته می‌شوند، خانوادهٔ زبان‌های باقاعده نامیده می‌شوند. هر چه یک ماشین قوی‌تر باشد، می‌تواند زبان‌های پیچیده‌تری را بپذیرد. ماشین‌های خودکاری که از این ماشین‌ها به‌شمار می‌آیند، عبارتند از: