نیم اتوماتون

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

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

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

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

یک نیم اتوماتون، یک سه تایی (Q,\Sigma,T) است که در آن \Sigma یک مجموعه ی ناتهی است و "الفبای ورودی" نامیده می شود، Q یک مجموعه ی ناتهی است که "مجموعه ی حالات" نامیده می شود و T تابع انتقال است.

T: Q\times \Sigma \to Q

هرگاه که مجموعه ی حالات Q یک مجموعه ی متناهی باشد، نیم اتوماتون می تواند به عنوان یک اتوماتای متناهی قطعی (Q,\Sigma,T,q_0,A) در نظر گرفته شود، البته بدون حالت اولیه ی q_0 یا مجموعه ی حالات پذیرش A. به طور متناوب نیم اتوماتون یک ماشین حالت متناهی است که خروجی ندارد و فقط ورودی دارد.

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

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

برای هر کلمه ی w در \Sigma^*، T_w:Q\to Q را تابعی قرار دهید که به صورت بازگشتی برای تمام q \in Q به صورت زیر تعریف شده است:

  • اگر w=\varepsilon، آنگاه T_\varepsilon(q)=q، بنا بر این کلمه ی تهی \varepsilon وضعیت را تغییر نمی دهد.
  • اگر w=\sigma یک حرف در \Sigma باشد، آنگاه T_\sigma(q)=T(q,\sigma).
  • اگر برای \sigma\in\Sigma و v\in \Sigma^* داشته باشیم w=\sigma v، آنگاه T_w(q)=T_v(T_\sigma(q)) .

M(Q,\Sigma,T) را مجموعه ی زیر قرار دهید:

M(Q,\Sigma,T)=\{T_w \vert w\in\Sigma^* \}.

مجموعه ی M(Q,\Sigma,T) تحت عمل ترکیب تابع بسته است؛ بنا بر این برای تمام v,w\in\Sigma^* ها می توان نوشت T_w\circ T_v=T_{vw}. همچنین این مجموعه شامل T_\varepsilon است که شامل تابع همانی روی S است. از آنجایی که ترکیب توابع دارای خاصیت انجمنی است، مجموعه ی M(Q,\Sigma,T) یک مونوئید است که مونوئید ورودی، مونوئید مشخصه، نیم گروه مشخصه یا مونوئید انتقال برای نیم اتوماتون (Q,\Sigma,T) نامیده می شود.

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

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

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

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

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