Finite State Machine

این برنامه پیاده سازی یک الگوریتم برای کاهش یک ماشین حالت محدود.

ماشین‌های حالات متناهی (Finite state machines) اختصاراً FA، به مدل‌هایی مجرد[۱] از ماشین‌ها [۲] اطلاق می‌گردد که قادرند در مجموعه‌ای متناهی از حالات[۳] وجود داشته باشند.

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