مترجم دوگانه

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

Julius Richard Büchi

مقدمه

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

تعریف

یک زبان امگا جزئی از کلاس منظم امگا است اگر حداقل یکی شروط زیر را داشته باشد:

$A^{\omega }$ که $A$ یک زبان غیر تهی است که شامل رشته به طول صفر نمی‌شود.
$A B$ که $A$ یک زبان منظم و $B$ یک زبان منظم امگا است.
$A\cup B$ که $A, B$ هرکدام یک زبان منظم امگا هستند.

این ویژگی‌ها شباهت زیادی به ویژگی‌های زبان‌های منظم دارد.

مشکلات تشخیص

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

تشخیص

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

تشخیص زبان امگا منظم، $L$

، به این ترتیب است که اگر برای هر کلمه محدودی که تا زمان مشخصی مشاهده می‌شود، مانند

u

می‌توان یک کلمه محدود دیگر را مثل

v

به آن اضافه کرد، به طوری که

u v

یک «پیش اطلاعات محدود» برای

L

است. برای هر کلمه نامحدود

w

، ما این مفهوم را می‌دانیم که

u v w

یا در

L

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

برابری با اتوماتای بوچی

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

انواع زیر بخش

ωB-regular language , ωS-regular language, ωT-regular language