مترجم دوگانه یا مترجم زبان های منظم امگا ( به انگلیسی: Omega - regular language ) مربوط به بخش منظم از زبان های امگا ( به انگلیسی: Omega language ) می باشد که برای تشخیص و تحلیل آن ها به کار می رود. برای اولین بار در سال ۱۹۶۲ توسط بوچی ( به انگلیسی: Büchi ) این موضوع نشان داده شد که زبان های منظم امگا در حالت دقیقی قابل توصیف می باشند.
زبانهای ω به مجموعه رشته هایی گفته می شود که لزوماً هر کدام از آن ها متناهی نیستند. زبان منظم امگا یک بخشی از این تعریف هستند، به این صورت که یک کلاس می باشند. یعنی مجموعه زبان هایی را شامل می شود که منظم اند و لزوماً متناهی و دارای رشته های به طول متناهی نیستند. یکی از مسائلی که برای این زبان ها وجود دارد این است که به دلیل این که اندازه آن ها متناهی نیست، به روش های گذشته نمی توان برای آن ها مترجم ساخت و نیاز به یک مترجم جدید دارند.
یک زبان امگا جزئی از کلاس منظم امگا است اگر حداقل یکی شروط زیر را داشته باشد:
• A ω {\displaystyle A^{\omega }} که A {\displaystyle A} یک زبان غیر تهی است که شامل رشته به طول صفر نمی شود.
• A B {\displaystyle AB} که A {\displaystyle A} یک زبان منظم و B {\displaystyle B} یک زبان منظم امگا است.
• A ∪ B {\displaystyle A\cup B} که A , B {\displaystyle A, B} هرکدام یک زبان منظم امگا هستند.
این ویژگی ها شباهت زیادی به ویژگی های زبان های منظم دارد.
یکی از مشکلاتی که در تشخیص این زبان ها وجود دارد این است که برای تشخیص آن ها در زمان اجرا، ما تنها می توانیم تعداد محدودی واژه را در هر زمان خوانده باشیم ولی طول رشته های این زبان می تواند نامتناهی باشد.
زبان های منظم امگا نقش مهمی را در دقیق سازی و تأییدکنندگی در بسیاری از روش های نظارت بر سیستم ها، در طول زمان اجرا ایفا می کنند. با این حال، از آنجا که عناصر آن ها کلمات بی نهایت است، هر زبان امگا منظم می تواند در زمان اجرا مشاهده و تشخیص پذیرد. زمانی که تنها یک زیررشته محدود از یک رشته طولانی تر، تاکنون مشاهده شده است ما چگونه باید تشخیص دهیم رشته اصلی عضو زبان می باشد یا خیر؟
تشخیص زبان امگا منظم، L ، به این ترتیب است که اگر برای هر کلمه محدودی که تا زمان مشخصی مشاهده می شود، مانند u می توان یک کلمه محدود دیگر را مثل v به آن اضافه کرد، به طوری که u v یک «پیش اطلاعات محدود» برای L است. برای هر کلمه نامحدود w ، ما این مفهوم را می دانیم که u v w یا در L می باشد یا خیر. این مفهوم در گذشته توسط چند نویسنده مورد مطالعه قرار گرفته و شناخته شده است که کلاس زبان های قابل کنترل بسیار واضح تر می باشند. به عنوان مثال: زبان های رایجی که تحت عنوان زبان های امن استفاده می شوند. اما طبقه بندی دقیق زبان های قابل کنترل تا کنون بسیار دشوار و انجام نشده بوده است.
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفزبانهای ω به مجموعه رشته هایی گفته می شود که لزوماً هر کدام از آن ها متناهی نیستند. زبان منظم امگا یک بخشی از این تعریف هستند، به این صورت که یک کلاس می باشند. یعنی مجموعه زبان هایی را شامل می شود که منظم اند و لزوماً متناهی و دارای رشته های به طول متناهی نیستند. یکی از مسائلی که برای این زبان ها وجود دارد این است که به دلیل این که اندازه آن ها متناهی نیست، به روش های گذشته نمی توان برای آن ها مترجم ساخت و نیاز به یک مترجم جدید دارند.
یک زبان امگا جزئی از کلاس منظم امگا است اگر حداقل یکی شروط زیر را داشته باشد:
• A ω {\displaystyle A^{\omega }} که A {\displaystyle A} یک زبان غیر تهی است که شامل رشته به طول صفر نمی شود.
• A B {\displaystyle AB} که A {\displaystyle A} یک زبان منظم و B {\displaystyle B} یک زبان منظم امگا است.
• A ∪ B {\displaystyle A\cup B} که A , B {\displaystyle A, B} هرکدام یک زبان منظم امگا هستند.
این ویژگی ها شباهت زیادی به ویژگی های زبان های منظم دارد.
یکی از مشکلاتی که در تشخیص این زبان ها وجود دارد این است که برای تشخیص آن ها در زمان اجرا، ما تنها می توانیم تعداد محدودی واژه را در هر زمان خوانده باشیم ولی طول رشته های این زبان می تواند نامتناهی باشد.
زبان های منظم امگا نقش مهمی را در دقیق سازی و تأییدکنندگی در بسیاری از روش های نظارت بر سیستم ها، در طول زمان اجرا ایفا می کنند. با این حال، از آنجا که عناصر آن ها کلمات بی نهایت است، هر زبان امگا منظم می تواند در زمان اجرا مشاهده و تشخیص پذیرد. زمانی که تنها یک زیررشته محدود از یک رشته طولانی تر، تاکنون مشاهده شده است ما چگونه باید تشخیص دهیم رشته اصلی عضو زبان می باشد یا خیر؟
تشخیص زبان امگا منظم، L ، به این ترتیب است که اگر برای هر کلمه محدودی که تا زمان مشخصی مشاهده می شود، مانند u می توان یک کلمه محدود دیگر را مثل v به آن اضافه کرد، به طوری که u v یک «پیش اطلاعات محدود» برای L است. برای هر کلمه نامحدود w ، ما این مفهوم را می دانیم که u v w یا در L می باشد یا خیر. این مفهوم در گذشته توسط چند نویسنده مورد مطالعه قرار گرفته و شناخته شده است که کلاس زبان های قابل کنترل بسیار واضح تر می باشند. به عنوان مثال: زبان های رایجی که تحت عنوان زبان های امن استفاده می شوند. اما طبقه بندی دقیق زبان های قابل کنترل تا کنون بسیار دشوار و انجام نشده بوده است.
wiki: مترجم دوگانه