کدامیک از موارد زیر غلط است؟!!
الف)اگر G1 بدون محدودیت و G2 منظم باشد آنگاه[tex]L\left ( G1 \right ) \cap L\left ( G2 \right )= \phi[/tex] همواره تصمصم ناپذیر است.
ب)هیچ الگوریتمی برای تصمیم پذیری [tex]L\left ( G1 \right ) \cap L\left ( G2 \right )= \phi[/tex] به شرطی که هردو مستقل از متن باشند وجود ندارد
ج)اگر G1 گرامر منظمی باشد آنگاه [tex]L\left ( G1 \right ) = L\left ( G2 \right )[/tex] به شرطی که G2 منظم
باشد تصمصم پذیر اما اگر G2 بدون محدودیت یا مستقل از متن باشد تصمیم ناپذیر است
۱/الف ۲/ب ۳/ج ۴/هرسه مورد صحیح است
ج/
اگر G1 گرامر منظمی باشد آنگاه به شرطی که G2 منظم یا مستقل از متن
باشد تصمصم پذیر(برابری) است اما اگر G2 بدون محدودیت باشد تصمیم ناپذیر است
به نظرتون مورد الف غلط نیست؟
(۱۱ بهمن ۱۳۹۱ ۰۷:۳۹ ق.ظ)fsi2013 نوشته شده توسط: به نظرتون مورد الف غلط نیست؟
البته چون در گزینه ی اول از کلمه همواره استفاده کرده، بله اینم می تونه غلط باشه.
مثال:
اگر
G1=[tex]a^{n}b^{n}c^{n}[/tex]
G2=[tex]\Theta[/tex]
باشه اشتراک بین این دو G2 میشه که یک زبان منظمه و بررسی برابری در زبانهای منظم یک مسئله ی تصمیم پذیره.
افرین برتو! شیطون لینز و خوندی
منم همینو میگم کلمه ی همواره اش غلطه اگ یه کم با دقت تر طراحی میکردم یا اشتباه میزدی یا غلط میزدی 
)
دوستان هر نکته ای هست اضافه کنید لطفا
۴ روز دیگه امتحانه
-
تورینک دو نواره اگر از مرتبه ی n باشد تورینگ استاندارد از مرتبه n^2
کلا اگ یه مسئله ای بود که تورینگ تک نواره اونو با n^4 حل کرده بود با دو نوارده با n^2 حل میشه
اینارو Oبزرگ در نظر بگیرید