مبدل با حالت محدود
مبدل با حالت محدود (انگلیسی:Finite-state transducer)، ماشین حالت محدودی است که دو یا بیشتر از دو نوار ورودی دارد. حالت سادهاش دو نوار یکی نوار ورودی و دیگری نوار خروجی دارد که با خواندن از روی نوار ورودی، نوار خروجی را ایجاد میکند.
تفاوت مبدل با حالت متناهی با ماشین با حالت متناهی در این است که ماشین تنها برای تشخیص اینکه رشتهای در زبان منظم است به کار میرود ولی مبدل علاوه بر تشخیص وجود رشته، رشتهٔ خروجی را از رشته ورودی میسازد. در واقع این مبدل شکل بسط داده شدهای از ماشین با حالت متناهی است و دو مجموعه از نمادها را به هم مینگارد و مترجم و مربوطکننده رشته دو نوار تعبیر میشود.
تعریف رسمی
یک مبدل حالت متناهی را با ۶ تاپل (چندتایی)
- : مجموعه متناهی از حالتهایی که یک مبدل میتواند داشته باشد.
- : مجموعه متناهی که نمادها و الفبای نوار ورودی را مشخص میکند.
- : مجموعه متناهی که نمادها و الفبای نوار خروجی را تشکیل میدهد.
- : زیر مجموعهای ازاست که حالتهای شروع مبدل را تشکیل میدهد.
- : زیر مجموعهای ازاست که حالتهای نهایی و موردقبول ماشین را نمایش میدهد.
- : رابطهٔ هر انتقال بین حالتها را در مبدل نمایش میدهد. (برای نمایش رشته خالی است)
نحوه نمایش
برای نمایش مبدل حالت متناهی میتوانیم از گراف جهتدار که گراف انتقال نیز نامیده میشود استفاده کنیم. راسهای این گراف، مجموعه حالتهای مبدل اند و
شکل زیر یه نمونه ساده ای از این مبدل است:
این مبدل روی زبان با الفبای {۰٬۱} تعریف شدهاست. یال ۰:۱ به این معنی است که در این انتقال، مبدل نماد ۰ را از نوار اولی میخواند و در دومین نوار مینویسد.
انواع مبدلها
برحسب اینکه از کدام نوار بخواند و در کدام نوار بنویسد، مبدل به چند نوع تبدیل میشود. نوع تولیدکننده، که قادر است در هر دو نوار بنویسد و نوع تشخیص دهنده که قادر است از هر دو نوار بخواند. نوع چپ به راست، از نوار اول میخواند و در نوار دوم مینویسد و نوع راست به چپ هم برعکس قبلی عمل میکند.
مبدل حالت محدود وزندار
با افزودن وزن به هر یک از انتقالات مبدل با حالت متناهی، مبدل وزندار آن تشکیل میشود. ایده این نوع مبدل تنها در وجود وزن به انتقالها نیست، بلکه یک سطحی از مفاهیم ریاضی را که به نام نیم-حلقه را در مبدلها را موجب میشود. در واقع این مفهوم ریاضی مشخص میکند چگونه در طی عملیاتها روی مبدل، این وزن انتقالها ترکیب میشود.
این نوع مبدل در پردازش زبان طبیعی و تشخیص گفتار کاربرد فراوانی دارد.
روابط منظم
همانطور که ماشین حالت محدود، هم متناظر زبانهای منظم است، مبدل حالت محدود نیز متناظر روابط منظم و نمایش دهندهٔ آنهاست. روابط منظم، مجموعه از زوج رشتههایی هستند که تحت قواعدی به هم نظیر شدهاند. همانند زبانهای منظم، تحت اجتماع بستهاند ولی تحت تفاضل و مکملگیری و اشتراک بسته نیستند. (البته بیشتر روابط منظم که در آن از
کاربردها
مبدل با حالت محدود، کاربرهای فراوانی هم در کامپایلرها و هم در حوزه پردازش زبان طبیعی دارد.
صرف افعال
رای پیدا کردن ریشه کلمهها و حالت سادهٔ آنها میتوان استفاده کرد. مثلاً گلها ←گل، میرود ← رو.
تجزیه تکواژشناسی
جهت به دست آوردن ویژگیها و ساختار یک واژه از جمله اسم یا فعل کاربرد دارد. مثلاً رایانهها ← اسم + علامت جمع
ترجمه ساده بین زبانها
برای مثال ترجمه از زبان فارسی به انگلیسی (به صورت کلمه به کلمه)
دستورهای ساده ساختهشده برای رایانه
در ترجمه دستورهای صوتی که به وسیله الکترونیکی از طریق دستیار شخصی صوتی هوشمند مثل نرمافزارهایی همچون سیری، وارد میشود نیز کاربرد مورد استفاده است.
منابع
- ↑ [[[:en:Finite-state transducer]] «Finite-state transducer»].
- ↑ «Finite State Transducers».
- ↑ Philip N. Garner (December 2007). "A Weighted Finite State Transducer tutorial" (PDF) (به انگلیسی).
- ↑ Daniel Jurafsky & James H. (اکتبر ۱۲, ۲۰۰۷). Speech and Language Processing: An introduction to speech recognition, natural language processing, and computational linguistics. صص. فصل ۳ - صفحه ۱۴.
- ↑ Mehryar Mohri1 , Fernando Pereira2 and Michael Riley. "Weighted Finite-State Transducers in Speech Recognition" (PDF) (به انگلیسی). ;
برای مطالعهٔ بیشتر
- مهریار مهری . Weighted Finite-State Transducer Algorithms An Overview، تاریخ: ۱۴ مه ۲۰۰۴
- Fernando Pereira- Michael Riley - مهریار مهری، Weighted Finite-State Transducers in Speech Recognition.