نیم اتوماتون

در ریاضیات و علوم کامپیوتر، یک نیم اتوماتون، یک اتوماتون قطعی حالت متناهی است که ورودی دارد و هیچ خروجی ندارد. نیم اتوماتون شامل یک مجموعه 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 متناهی یا حتی شمارش پذیر باشد. به عنوان مثال می توان به نیم اتوماتایی که تحت پشتیبانی مفهوم اتوماتای کوانتومی متناهی هستند اشاره کرد.

منابع

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