نیم اتوماتون

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

در ریاضیات و علوم کامپیوتر، یک نیم اتوماتون، یک اتوماتون قطعی حالت متناهی است که ورودی دارد و هیچ خروجی ندارد. نیم اتوماتون شامل یک مجموعه Q از حالت ها، یک مجموعه Σ که الفبای ورودی نامگذاری می شود و یک تابع T: Q × Σ → Q که تابع انتقال نامیده می شود است.

در رابطه با هر نیم اتوماتون یک مونوئید وجود دارد که مونوئید مشخصه، مونوئید ورودی، مونوئید انتقال یا سیستم انتقال نیم اتوماتون نامیده می شود که روی مجموعه حالت های Q عمل می کند. این مونوئید می تواند به عنوان یک عمل از مونوئید آزاد رشته ها روی الفبای Σ دیده شود، یا به عنوان نیم گروه انتقالی ناشی شده از Q.

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

یک نیم اتوماتون، یک سه تایی است که در آن یک مجموعه ی ناتهی است و "الفبای ورودی" نامیده می شود، یک مجموعه ی ناتهی است که "مجموعه ی حالات" نامیده می شود و تابع انتقال است.

هرگاه که مجموعه ی حالات یک مجموعه ی متناهی باشد، نیم اتوماتون می تواند به عنوان یک اتوماتای متناهی قطعی در نظر گرفته شود، البته بدون حالت اولیه ی یا مجموعه ی حالات پذیرش A. به طور متناوب نیم اتوماتون یک ماشین حالت متناهی است که خروجی ندارد و فقط ورودی دارد.

هر نیم اتوماتون، باعث ایجاد یک عمل مونوئید به طریق زیر می شود.

فرض کنید یک مونوئید آزاد باشد که به وسیله ی الفبای تولید شده است؛ در این صورت مجموعه ی تمام رشته های با طول متناهی از حروف الفبای است.

برای هر کلمه ی w در ، را تابعی قرار دهید که به صورت بازگشتی برای تمام به صورت زیر تعریف شده است:

  • اگر ، آنگاه ، بنا بر این کلمه ی تهی وضعیت را تغییر نمی دهد.
  • اگر یک حرف در باشد، آنگاه .
  • اگر برای و داشته باشیم ، آنگاه .

را مجموعه ی زیر قرار دهید:

مجموعه ی تحت عمل ترکیب تابع بسته است؛ بنا بر این برای تمام ها می توان نوشت . همچنین این مجموعه شامل است که شامل تابع همانی روی S است. از آنجایی که ترکیب توابع دارای خاصیت انجمنی است، مجموعه ی یک مونوئید است که مونوئید ورودی، مونوئید مشخصه، نیم گروه مشخصه یا مونوئید انتقال برای نیم اتوماتون نامیده می شود.

خصوصیات[ویرایش]

اگر مجموعه ی حالات Q متناهی باشد، آنگاه توابع انتقال به طور معمول به شکل جدول های انتقال حالت نشان داده می شوند. ساختار تمام انتقال های ممکن مشتق شده از رشته ها در گروه آزاد، یک نمایش گرافیکی شبیه به گراف دی براین دارد.

نیازی نیست که مجموعه ی حالات Q متناهی یا حتی شمارش پذیر باشد. به عنوان مثال می توان به نیم اتوماتایی که تحت پشتیبانی مفهوم اتوماتای کوانتومی متناهی هستند اشاره کرد.

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

ویکی پدیای انگلیسی