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

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

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

== تعریف رسمی ==
یک مبدل حالت متناهی را با ۶ تاپل (چندتایی)<math>(Q, \Sigma, \Gamma, T, F, \delta)</math> نمایش می‌دهند:
* <math>Q</math> : [[مجموعه متناهی]] از حالت‌هایی که یک مبدل می‌تواند داشته باشد.
* <math>\Sigma</math>: مجموعه متناهی که نمادها و الفبای نوار ورودی را مشخص می‌کند.
* <math>\Gamma</math>: مجموعه متناهی که نمادها و الفبای نوار خروجی را تشکیل می‌دهد.
* <math>\Iota</math>: [[زیرمجموعه|زیر مجموعه]]<nowiki/>ای از <math>Q</math>است که حالت‌های شروع مبدل را تشکیل می‌دهد.
* <math>F</math>: زیر مجموعه‌ای از <math>Q</math> است که حالت‌های نهایی و موردقبول ماشین را نمایش می‌دهد.
* <math>\delta \subseteq Q \times (\Sigma\cup\{\epsilon\}) \times (\Gamma\cup\{\epsilon\}) \times Q</math>: رابطهٔ هر انتقال بین حالت‌ها را در مبدل نمایش می‌دهد. (<math>\epsilon</math>برای نمایش [[رشته خالی]] است)<ref name=":02">{{یادکرد وب|نویسنده=|کد زبان=|تاریخ=|وبگاه=|نشانی=[[:en:Finite-state transducer]]|عنوان=Finite-state transducer}}</ref>

== نحوه نمایش ==
برای نمایش مبدل حالت متناهی می‌توانیم از [[گراف جهت‌دار]] که گراف انتقال نیز نامیده می‌شود استفاده کنیم. راس‌های این گراف، مجموعه حالت‌های مبدل اند و <math>(q,a,b,r)\in\delta</math>به معنی وجود یالی از رأس <math>q</math>به رأس <math>r</math>است که نماد <math>a</math>برچسب ورودی و <math>b</math>برچست خروجی یال است و متناسب با نوع مبدل، در دو نوار اعمال می‌شود.<ref name=":02"/>

شکل زیر یه نمونه ساده ای از این مبدل است:
[[پرونده:Example_for_finite_state_transducer_functions.png|پیوند=[[پرونده:Example for finite state transducer functions.png]]|وسط|بی‌قاب]]
این مبدل روی زبان با الفبای {۰٬۱} تعریف شده‌است. یال ۰:۱ به این معنی است که در این انتقال، مبدل نماد ۰ را از نوار اولی می‌خواند و در دومین نوار می‌نویسد.

== انواع مبدل‌ها ==
برحسب اینکه از کدام نوار بخواند و در کدام نوار بنویسد، مبدل به چند نوع تبدیل می‌شود. نوع تولیدکننده، که قادر است در هر دو نوار بنویسد و نوع تشخیص دهنده که قادر است از هر دو نوار بخواند. نوع چپ به راست، از نوار اول می‌خواند و در نوار دوم می‌نویسد و نوع [[راست‌به‌چپ|راست به چپ]] هم برعکس قبلی عمل می‌کند.<ref>{{یادکرد وب|نویسنده=|کد زبان=|تاریخ=|وبگاه=|نشانی=http://cs.union.edu/~striegnk/courses/nlp-with-prolog/html/node13.html|عنوان=Finite State Transducers}}</ref>

=== مبدل حالت محدود وزن‌دار ===
با افزودن وزن به هر یک از انتقالات مبدل با حالت متناهی، مبدل وزن‌دار آن تشکیل می‌شود. ایده این نوع مبدل تنها در وجود وزن به انتقال‌ها نیست، بلکه یک سطحی از مفاهیم ریاضی را که به نام [[نیم-حلقه]] را در مبدل‌ها را موجب می‌شود. در واقع این مفهوم ریاضی مشخص می‌کند چگونه در طی عملیات‌ها روی مبدل، این وزن انتقال‌ها ترکیب می‌شود.<ref>{{یادکرد وب|نویسنده=Philip N. Garner|کد زبان=en|تاریخ=December 2007|وبگاه=|نشانی=http://publications.idiap.ch/downloads/reports/2008/pgarner-idiap-com-08-03.pdf|عنوان=A Weighted Finite State
Transducer tutorial}}</ref>

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

== روابط منظم ==
همان‌طور که ماشین حالت محدود، هم متناظر زبان‌های منظم است، مبدل حالت محدود نیز متناظر روابط منظم و نمایش دهندهٔ آنهاست. روابط منظم، مجموعه از زوج رشته‌هایی هستند که تحت قواعدی به هم نظیر شده‌اند. همانند زبان‌های منظم، تحت اجتماع بسته‌اند ولی تحت تفاضل و مکمل‌گیری و اشتراک بسته نیستند. (البته بیشتر روابط منظم که در آن از <math>\epsilon</math>استفاده نشده‌است، به احتمال زیاد تحت این عملیات‌ها بسته هستند)<ref name=":1">{{یادکرد کتاب|عنوان=Speech and Language Processing: An introduction to speech recognition, natural
language processing, and computational linguistics|نام خانوادگی=Daniel Jurafsky & James H.|نام=|ناشر=|سال=October 12, 2007|شابک=|مکان=|صفحات=فصل 3 - صفحه 14}}</ref>

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

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

=== تجزیه [[تکواژشناسی]] ===
جهت به دست آوردن ویژگی‌ها و ساختار یک واژه از جمله اسم یا فعل کاربرد دارد. مثلاً رایانه‌ها ← اسم + علامت جمع<ref name=":1"/>

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

=== دستورهای ساده ساخته‌شده برای رایانه ===
در ترجمه دستورهای صوتی که به وسیله الکترونیکی از طریق دستیار شخصی صوتی هوشمند مثل نرم‌افزارهایی همچون [[سیری (نرم‌افزار)|سیری]]، وارد می‌شود نیز کاربرد مورد استفاده است.<ref>{{یادکرد وب|نویسنده=Mehryar Mohri1
, Fernando Pereira2 and Michael Riley|کد زبان=en|تاریخ=|وب‌گاه=|نشانی=https://cs.nyu.edu/~mohri/pub/csl01.pdf|عنوان=Weighted Finite-State Transducers in
Speech Recognition}}</ref>

== منابع ==
{{پانویس|۲}}

== برای مطالعهٔ بیشتر ==
* [[مهریار مهری]] . [https://cs.nyu.edu/~mohri/pub/fla.pdf Weighted Finite-State Transducer Algorithms An Overview]، تاریخ: ۱۴ مه ۲۰۰۴
* [[Fernando Pereira]]- [[Michael Riley]] - مهریار مهری، [https://cs.nyu.edu/~mohri/pub/csl01.pdf Weighted Finite-State Transducers in Speech Recognition].

[[رده:اتوماتا (مکانیک)]]
[[رده:روش‌های صوری]]
[[رده:زبان‌های صوری]]
[[رده:ماشین متناهی]]
[[رده:مدل‌های محاسباتی]]
[[رده:نظریه اتوماتا]]
[[رده:ویکی‌سازی رباتیک]]