Finite state machines

ماشین حالات متناهی

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

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