مبدل با حالت محدود

مبدل با حالت محدود ( انگلیسی:Finite - state transducer ) ، ماشین حالت محدودی است که دو یا بیشتر از دو نوار ورودی دارد. حالت ساده اش دو نوار یکی نوار ورودی و دیگری نوار خروجی دارد که با خواندن از روی نوار ورودی، نوار خروجی را ایجاد می کند.
تفاوت مبدل با حالت متناهی با ماشین با حالت متناهی در این است که ماشین تنها برای تشخیص اینکه رشته ای در زبان منظم است به کار می رود ولی مبدل علاوه بر تشخیص وجود رشته، رشتهٔ خروجی را از رشته ورودی می سازد. در واقع این مبدل شکل بسط داده شده ای از ماشین با حالت متناهی است و دو مجموعه از نمادها را به هم می نگارد و مترجم و مربوط کننده رشته دو نوار تعبیر می شود.
یک مبدل حالت متناهی را با ۶ تاپل ( چندتایی ) ( Q , Σ , Γ , T , F , δ ) نمایش می دهند:
• Q {\displaystyle Q}   : مجموعه متناهی از حالت هایی که یک مبدل می تواند داشته باشد.
• Σ {\displaystyle \Sigma } : مجموعه متناهی که نمادها و الفبای نوار ورودی را مشخص می کند.
• Γ {\displaystyle \Gamma } : مجموعه متناهی که نمادها و الفبای نوار خروجی را تشکیل می دهد.
• I {\displaystyle \mathrm {I} } : زیر مجموعهای از Q {\displaystyle Q} است که حالت های شروع مبدل را تشکیل می دهد.
• F {\displaystyle F} : زیر مجموعه ای از Q {\displaystyle Q} است که حالت های نهایی و موردقبول ماشین را نمایش می دهد.
• δ ⊆ Q × ( Σ ∪ { ϵ } ) × ( Γ ∪ { ϵ } ) × Q {\displaystyle \delta \subseteq Q\times ( \Sigma \cup \{\epsilon \} ) \times ( \Gamma \cup \{\epsilon \} ) \times Q} : رابطهٔ هر انتقال بین حالت ها را در مبدل نمایش می دهد. ( ϵ {\displaystyle \epsilon } برای نمایش رشته خالی است ) [ ۱]
برای نمایش مبدل حالت متناهی می توانیم از گراف جهت دار که گراف انتقال نیز نامیده می شود استفاده کنیم. راس های این گراف، مجموعه حالت های مبدل اند و ( q , a , b , r ) ∈ δ به معنی وجود یالی از رأس q به رأس r است که نماد a برچسب ورودی و b برچست خروجی یال است و متناسب با نوع مبدل، در دو نوار اعمال می شود. [ ۱]
شکل زیر یه نمونه ساده ای از این مبدل است:
این مبدل روی زبان با الفبای {۰٬۱} تعریف شده است. یال ۰:۱ به این معنی است که در این انتقال، مبدل نماد ۰ را از نوار اولی می خواند و در دومین نوار می نویسد.