ماشین میلی

ماشین میلی (به انگلیسی: mealy machine) در نظریه محاسبات یک نوع از ماشین‌های حالات متناهی ست که خروجی آن به حالت کنونی و مقدار ورودی کنونی وابسته‌است. (این ماشین نقطهٔ مقابل ماشین مور است که خروجی آن فقط به حالت کنونی آن وابسته می‌باشد)

فرم تعریف شده[ویرایش]

ماشین میلی به شکل یک شش‌تایی (S, S0, Σ, Λ, T, G) است که در آن:

S:مجموعه‌ای از حالات متناهی‌ست.
S0: حالت آغازین یا حالت شروع که زیر مجموعه‌ای از S است.
Σ: مجموعه‌ای متناهی از الفبای ورودی‌ست.
Λ: مجموعه‌ای متناهی از الفبای خروجی‌ست.
T: S × Σ → S: تابع انتقال است که حالت و الفبای ورودی را به حالت بعدی منتقل می‌کند.
G: S × Σ → Λ: تابع خروجی‌ست که جفتی از حالت و اسمبل ورودی را به سمبل خروجی تبدیل می‌کند.

در برخی فرمول نویسی‌ها توابع انتقال و ورودی در یک تابع ادغام شده و به این صورت در می‌آیند: T: S × Σ → S × Λ

نمودار[ویرایش]

نمودار حالت برای ماشین میلی شامل نقاط تقاطع ارزش خروجی با هر لبهٔ انتقال است (در مقایسه با ماشین مور که شامل نقاط تقاطع ارزش خروجی و هر حالت است)

انواع[ویرایش]

ساده[ویرایش]

یک ماشین میلی ساده یک ورودی و یک خروجی دارد. هر لبهٔ انتقال با یک مقدار ورودی (که در تصویر با رنگ قرمز نشان داده شده) و یک مقدار خروجی (رنگ آبی) برچسب گذاری شده. حالت شروع ماشین Si است.

پیچیده[ویرایش]

ماشین میلی پیچیده می‌تواند تعداد بیشتری ورودی و خروجی داشته باشد.

کاربردها[ویرایش]

ماشین‌های میلی یک مدل ریاضی ابتدایی برای ماشین‌های رمزگذاری شده فراهم می‌کنند. در نظر بگیرید که ورودی و خروجی ما حروف الفبای لاتین باشند، به عنوان مثال آنگاه یک ماشین میلی می‌تواند طراحی شود که یک رشته را دریافت کند و آن را به یک رشته کدگذاری شده تبدیل کند.