ماشین میلی
ماشین میلی (به انگلیسی: mealy machine) در نظریه محاسبات یک نوع از ماشین‌های حالات متناهی ست که خروجی آن به حالت کنونی و مقدار ورودی کنونی وابسته‌است. (این ماشین نقطهٔ مقابل ماشین مور است که خروجی آن فقط به حالت کنونی آن وابسته می‌باشد)
فرم تعریف شده
ماشین میلی به شکل یک شش‌تایی (S, S0, Σ, Λ, T, G) است که در آن:
- S:مجموعه‌ای از حالات متناهی‌ست.
- S0: حالت آغازین یا حالت شروع که زیر مجموعه‌ای از S است.
- Σ: مجموعه‌ای متناهی از الفبای ورودی‌ست.
- Λ: مجموعه‌ای متناهی از الفبای خروجی‌ست.
- T: S × Σ → S: تابع انتقال است که حالت و الفبای ورودی را به حالت بعدی منتقل می‌کند.
- G: S × Σ → Λ: تابع خروجی‌ست که جفتی از حالت و اسمبل ورودی را به سمبل خروجی تبدیل می‌کند.
در برخی فرمول نویسی‌ها توابع انتقال و ورودی در یک تابع ادغام شده و به این صورت در می‌آیند: T: S × Σ → S × Λ
نمودار
نمودار حالت برای ماشین میلی شامل نقاط تقاطع ارزش خروجی با هر لبهٔ انتقال است (در مقایسه با ماشین مور که شامل نقاط تقاطع ارزش خروجی و هر حالت است)
انواع
ساده
یک ماشین میلی ساده یک ورودی و یک خروجی دارد. هر لبهٔ انتقال با یک مقدار ورودی (که در تصویر با رنگ قرمز نشان داده شده) و یک مقدار خروجی (رنگ آبی) برچسب گذاری شده. حالت شروع ماشین Si است.
پیچیده
ماشین میلی پیچیده می‌تواند تعداد بیشتری ورودی و خروجی داشته باشد.
کاربردها
ماشین‌های میلی یک مدل ریاضی ابتدایی برای ماشین‌های رمزگذاری شده فراهم می‌کنند. در نظر بگیرید که ورودی و خروجی ما حروف الفبای لاتین باشند، به عنوان مثال آنگاه یک ماشین میلی می‌تواند طراحی شود که یک رشته را دریافت کند و آن را به یک رشته کدگذاری شده تبدیل کند.
منابع
- مشارکت‌کنندگان ویکی‌پدیا. «Mealy machine». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۳ مارس ۲۰۱۴.
شرح
Mealy, George H. (سپتامبر ۱۹۵۵). "A Method for Synthesizing Sequential Circuits". Bell System Technical Journal 34