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

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

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

تعریف رسمیویرایش

یک مبدل حالت متناهی را با ۶ تاپل (چندتایی)  نمایش می‌دهند:

  •   : مجموعه متناهی از حالت‌هایی که یک مبدل می‌تواند داشته باشد.
  •  : مجموعه متناهی که نمادها و الفبای نوار ورودی را مشخص می‌کند.
  •  : مجموعه متناهی که نمادها و الفبای نوار خروجی را تشکیل می‌دهد.
  •  : زیر مجموعهای از  است که حالت‌های شروع مبدل را تشکیل می‌دهد.
  •  : زیر مجموعه‌ای از   است که حالت‌های نهایی و موردقبول ماشین را نمایش می‌دهد.
  •  : رابطهٔ هر انتقال بین حالت‌ها را در مبدل نمایش می‌دهد. ( برای نمایش رشته خالی است)[۱]

نحوه نمایشویرایش

برای نمایش مبدل حالت متناهی می‌توانیم از گراف جهت‌دار که گراف انتقال نیز نامیده می‌شود استفاده کنیم. راس‌های این گراف، مجموعه حالت‌های مبدل اند و  به معنی وجود یالی از رأس  به رأس  است که نماد  برچسب ورودی و  برچست خروجی یال است و متناسب با نوع مبدل، در دو نوار اعمال می‌شود.[۱]

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

 

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

انواع مبدل‌هاویرایش

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

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

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

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

روابط منظمویرایش

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

کاربردهاویرایش

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

صرف افعالویرایش

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

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

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

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

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

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

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

منابعویرایش

  1. ۱٫۰ ۱٫۱ [[[:en:Finite-state transducer]] «Finite-state transducer»] مقدار |نشانی= را بررسی کنید (کمک).
  2. «Finite State Transducers».
  3. Philip N. Garner (December 2007). "A Weighted Finite State Transducer tutorial" (PDF). line feed character in |عنوان= at position 24 (help)
  4. ۴٫۰ ۴٫۱ Daniel Jurafsky & James H. (اکتبر ۱۲, ۲۰۰۷). Speech and Language Processing: An introduction to speech recognition, natural language processing, and computational linguistics. صص. فصل ۳ - صفحه ۱۴. کاراکتر line feed character در |عنوان= در موقعیت 79 (کمک)
  5. Mehryar Mohri1 , Fernando Pereira2 and Michael Riley. "Weighted Finite-State Transducers in Speech Recognition" (PDF). line feed character in |عنوان= at position 37 (help); line feed character in |نویسنده= at position 15 (help)

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