در نظریهٔ محاسبه، یک ماشین متناهی متغیر، یک ماشین متناهی غیر قطعی است که انتقال های آن به انتقال های وجودی و عمومی تقسیم می شود. به طور مثال، فرض کنید A یک ماشین متغیر باشد.
برای انتقال وجودی ( q , a , q 1 ∨ q 2 ) {\displaystyle (q,a,q_{1}\vee q_{2})} ،
Aبه طور غیر قطعی، با خواندن a تغییر به یکی از حالتهای یا را انتخاب می کند؛ بنابراین مانند یک ماشین غیر قطعی منظم رفتار می کند.
Aبه q 1 {\displaystyle q_{1}} و q 2 {\displaystyle q_{2}} حرکت می کند، در حالی که a را می خواند و رفتار ماشین موازی را شبیه سازی می کند.
توجه کنید که به دلیل کمی سازی سراسری، یک اجرا بوسیلهٔ درخت اجرا نمایش داده می شود. اگر یک درخت اجرا در w وجود داشته باشد که هر مسیر به یک حالت پذیرش ختم شود A کلمهٔ w را قبول می کند.یک قضیهٔ پایه ای می گوید که هر AFA با اجرای نوع مشابهی از ساختار مجموعهٔ توانی همانطور که برای انتقال از NFA به یک ماشین متناهی قطعی استفاده می شود، معادل یک ماشین متناهی غیر قطعی است. این ساختار، یک AFA با k وضعیت را به NFA با بیش از 2 k {\displaystyle 2^{k}} وضعیت تغییر می دهد.
برای انتقال وجودی ( q , a , q 1 ∨ q 2 ) {\displaystyle (q,a,q_{1}\vee q_{2})} ،
Aبه طور غیر قطعی، با خواندن a تغییر به یکی از حالتهای یا را انتخاب می کند؛ بنابراین مانند یک ماشین غیر قطعی منظم رفتار می کند.
Aبه q 1 {\displaystyle q_{1}} و q 2 {\displaystyle q_{2}} حرکت می کند، در حالی که a را می خواند و رفتار ماشین موازی را شبیه سازی می کند.
توجه کنید که به دلیل کمی سازی سراسری، یک اجرا بوسیلهٔ درخت اجرا نمایش داده می شود. اگر یک درخت اجرا در w وجود داشته باشد که هر مسیر به یک حالت پذیرش ختم شود A کلمهٔ w را قبول می کند.یک قضیهٔ پایه ای می گوید که هر AFA با اجرای نوع مشابهی از ساختار مجموعهٔ توانی همانطور که برای انتقال از NFA به یک ماشین متناهی قطعی استفاده می شود، معادل یک ماشین متناهی غیر قطعی است. این ساختار، یک AFA با k وضعیت را به NFA با بیش از 2 k {\displaystyle 2^{k}} وضعیت تغییر می دهد.
wiki: ماشین متناهی متغیر