مترجم دوگانه

مترجم دوگانه یا مترجم زبان‌های منظم امگا (به انگلیسی: Omega-regular language) مربوط به بخش منظم از زبان‌های امگا (به انگلیسی: Omega language) می‌باشد که برای تشخیص و تحلیل آن‌ها به کار می‌رود. برای اولین بار در سال ۱۹۶۲ توسط بوچی (به انگلیسی: Büchi) این موضوع نشان داده شد که زبان‌های منظم امگا در حالت دقیقی قابل توصیف می‌باشند.
بندانگشتی|Julius Richard Büchi

 مقدمه 
زبانهای ω به مجموعه رشته‌هایی گفته می‌شود که لزوماً هر کدام از آن‌ها متناهی نیستند. زبان منظم امگا یک بخشی از این تعریف هستند، به این صورت که یک کلاس می‌باشند. یعنی مجموعه زبان‌هایی را شامل می‌شود که منظم‌اند و لزوماً متناهی و دارای رشته‌های به طول متناهی نیستند. یکی از مسائلی که برای این زبان‌ها وجود دارد این است که به دلیل این که اندازه آن‌ها متناهی نیست، به روش‌های گذشته نمی‌توان برای آن‌ها مترجم ساخت و نیاز به یک مترجم جدید دارند.

 تعریف 
یک زبان امگا جزئی از کلاس منظم امگا است اگر حداقل یکی شروط زیر را داشته باشد:
  که  یک زبان غیر تهی است که شامل رشته به طول صفر نمی‌شود.
  که  یک زبان منظم و  یک زبان منظم امگا است.
 که  هرکدام یک زبان منظم امگا هستند.
این ویژگی‌ها شباهت زیادی به ویژگی‌های زبان‌های منظم دارد.

 مشکلات تشخیص 
یکی از مشکلاتی که در تشخیص این زبان‌ها وجود دارد این است که برای تشخیص آن‌ها در زمان اجرا، ما تنها می‌توانیم تعداد محدودی واژه را در هر زمان خوانده باشیم ولی طول رشته‌های این زبان می‌تواند نامتناهی باشد.

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

تشخیص زبان امگا منظم، ، به این ترتیب است که اگر برای هر کلمه محدودی که تا زمان مشخصی مشاهده می‌شود، مانند می‌توان یک کلمه محدود دیگر را مثل  به آن اضافه کرد، به طوری که  یک «پیش اطلاعات محدود» برای است. برای هر کلمه نامحدود ، ما این مفهوم را می‌دانیم که یا در می‌باشد یا خیر. این مفهوم در گذشته توسط چند نویسنده مورد مطالعه قرار گرفته و شناخته شده‌است که کلاس زبان‌های قابل کنترل بسیار واضح تر می‌باشند. به عنوان مثال: زبان‌های رایجی که تحت عنوان زبان‌های امن استفاده می‌شوند. اما طبقه‌بندی دقیق زبان‌های قابل کنترل تا کنون بسیار دشوار و انجام نشده بوده‌است.

 برابری با اتوماتای بوچی 
قضیه: یک زبان امگا معادل با اتوماتای بوچی (به انگلیسی: Büchi automaton) است اگر و تنها اگر عضو کلاس زبان‌های منظم امگا باشد.

 انواع زیر بخش 
ωB-regular language , ωS-regular language, ωT-regular language

 منابع 

 Omega-regular language
 Learning omega regular language, Dana Angluin and Dana Fisman, Yale University and University of Pennsylvania
 Monitorability of ω-regular languages, Andreas Bauer
 Beyond ωBS-regular Languages: ωT-regular Expressions and Counter-Check Automata, EPTCS
 Omega automata, TUM university
 Automata of infinity words, Paritosh K. Pandya
رده:زبان‌های صوری