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

مبدل با حالت محدود (انگلیسی:Finite-state transducer)، ماشین حالت محدودی است که دو یا بیشتر از دو نوار ورودی دارد. حالت ساده‌اش دو نوار یکی نوار ورودی و دیگری نوار خروجی دارد که با خواندن از روی نوار ورودی، نوار خروجی را ایجاد می‌کند.

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

تعریف رسمی

یک مبدل حالت متناهی را با ۶ تاپل (چندتایی)$(Q,\Sigma ,\Gamma ,T,F,\delta )$ نمایش می‌دهند:

• $Q$ : مجموعه متناهی از حالت‌هایی که یک مبدل می‌تواند داشته باشد.
• $\Sigma$: مجموعه متناهی که نمادها و الفبای نوار ورودی را مشخص می‌کند.
• $\Gamma$: مجموعه متناهی که نمادها و الفبای نوار خروجی را تشکیل می‌دهد.
• $\mathrm {I}$: زیر مجموعهای از $Q$است که حالت‌های شروع مبدل را تشکیل می‌دهد.
• $F$: زیر مجموعه‌ای از $Q$ است که حالت‌های نهایی و موردقبول ماشین را نمایش می‌دهد.
• $\delta \subseteq Q\times (\Sigma \cup \{\epsilon \})\times (\Gamma \cup \{\epsilon \})\times Q$: رابطهٔ هر انتقال بین حالت‌ها را در مبدل نمایش می‌دهد. ($\epsilon$برای نمایش رشته خالی است)

نحوه نمایش

برای نمایش مبدل حالت متناهی می‌توانیم از گراف جهت‌دار که گراف انتقال نیز نامیده می‌شود استفاده کنیم. راس‌های این گراف، مجموعه حالت‌های مبدل اند و $(q,a,b,r)\in \delta$به معنی وجود یالی از رأس $q$به رأس $r$است که نماد $a$برچسب ورودی و $b$برچست خروجی یال است و متناسب با نوع مبدل، در دو نوار اعمال می‌شود.

شکل زیر یه نمونه ساده ای از این مبدل است:

این مبدل روی زبان با الفبای {۰٬۱} تعریف شده‌است. یال ۰:۱ به این معنی است که در این انتقال، مبدل نماد ۰ را از نوار اولی می‌خواند و در دومین نوار می‌نویسد.

انواع مبدل‌ها

برحسب اینکه از کدام نوار بخواند و در کدام نوار بنویسد، مبدل به چند نوع تبدیل می‌شود. نوع تولیدکننده، که قادر است در هر دو نوار بنویسد و نوع تشخیص دهنده که قادر است از هر دو نوار بخواند. نوع چپ به راست، از نوار اول می‌خواند و در نوار دوم می‌نویسد و نوع راست به چپ هم برعکس قبلی عمل می‌کند.

مبدل حالت محدود وزن‌دار

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

این نوع مبدل در پردازش زبان طبیعی و تشخیص گفتار کاربرد فراوانی دارد.

روابط منظم

همان‌طور که ماشین حالت محدود، هم متناظر زبان‌های منظم است، مبدل حالت محدود نیز متناظر روابط منظم و نمایش دهندهٔ آنهاست. روابط منظم، مجموعه از زوج رشته‌هایی هستند که تحت قواعدی به هم نظیر شده‌اند. همانند زبان‌های منظم، تحت اجتماع بسته‌اند ولی تحت تفاضل و مکمل‌گیری و اشتراک بسته نیستند. (البته بیشتر روابط منظم که در آن از $\epsilon$استفاده نشده‌است، به احتمال زیاد تحت این عملیات‌ها بسته هستند)

کاربردها

مبدل با حالت محدود، کاربرهای فراوانی هم در کامپایلرها و هم در حوزه پردازش زبان طبیعی دارد.

صرف افعال

رای پیدا کردن ریشه کلمه‌ها و حالت سادهٔ آن‌ها می‌توان استفاده کرد. مثلاً گل‌ها ←گل، می‌رود ← رو.

تجزیه تکواژشناسی

جهت به دست آوردن ویژگی‌ها و ساختار یک واژه از جمله اسم یا فعل کاربرد دارد. مثلاً رایانه‌ها ← اسم + علامت جمع

ترجمه ساده بین زبان‌ها

برای مثال ترجمه از زبان فارسی به انگلیسی (به صورت کلمه به کلمه)

دستورهای ساده ساخته‌شده برای رایانه

در ترجمه دستورهای صوتی که به وسیله الکترونیکی از طریق دستیار شخصی صوتی هوشمند مثل نرم‌افزارهایی همچون سیری، وارد می‌شود نیز کاربرد مورد استفاده است.

برای مطالعهٔ بیشتر

• مهریار مهری . Weighted Finite-State Transducer Algorithms An Overview، تاریخ: ۱۴ مه ۲۰۰۴
• Fernando Pereira- Michael Riley - مهریار مهری، Weighted Finite-State Transducers in Speech Recognition.