ماشین میلی
ماشین میلی (به انگلیسی: 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