تالار گفتمان مانشت
زبان های مستقل از متن [tex]0^n1^n0^n[/tex] - نسخه‌ی قابل چاپ
زبان های مستقل از متن [tex]0^n1^n0^n[/tex] - majidfathi69 - 25 دى ۱۳۹۲ ۰۶:۱۴ ب.ظ

لطفا طریقه محاسبه مکمل این زبان را توضیح دهید.
[تصویر: 237431_du7ebu8a.jpg]

ممنون.

Sent from my C6903 using Tapatalk

RE: زبان های مستقل از متن [tex]0^n1^n0^n[/tex] - Jooybari - 25 دى ۱۳۹۲ ۰۶:۲۶ ب.ظ

سلام. مکملش رو میشه از اجتماع این ۳ زبان به دست آورد:
۱- صفرهای دو طرف برابر نباشه.
۲- تعداد صفرهای سمت چپ با ۱ها برابر نباشه.
۳- تعداد صفرهای سمت راست با ۱ها برابر نباشه.

عذرخواهی میکنم. زبانی که گفتم باید با مجموعه رشته هایی که به فرم [tex]0^i1^j0^k[/tex] نیستن اجتماع گرفته بشه.

RE: زبان های مستقل از متن [tex]0^n1^n0^n[/tex] - majidfathi69 - 26 دى ۱۳۹۲ ۰۶:۰۶ ب.ظ

ممنون.
ولی مثلا رشته ۰۱۰۱۰۱ در مکمل این زبان موجود است. ولی توسط مواردی که شما گفتی پوشش داده نمیشود.

Sent from my C6903 using Tapatalk

Re: زبان های مستقل از متن [tex]0^n1^n0^n[/tex] - jahanmanesh - 26 دى ۱۳۹۲ ۰۸:۱۸ ب.ظ

سلام این مستقل از متنه؟ شکلش که نشون میده مستقل از متن نیس. ولی مکملش میشه تمام رشته عایی که تووشون این ترکیب از رشته ها نباشن
Landa
۰۱۰
۰۰۱۱۰۰
۰۰۰۱۱۱۰۰۰
..
که مکملش میشه،همه رشتهایی که عبارات بالا توش نباشن،یه راه حل سادش اینه که عبارت بالا رو بسازیم و با خوندن یه صفر یا یک اضافه اونو نقضش کنیم
یه عبارت منظمش میشه
۰^n 1^m 0^j | n≠m
و همچنین n,m,j بزرگتر از صفر چون لاندا هم نمیتونه باشه توی مکملش
..یعنی برابر نباشن.
که در اینصورت با یه ماشین پشته ای اول n تا صفر میریزیم روو پشته و با یه یک به حالت بعدی میریم و چیزی نمیخونیم و چیزیم روو پشته نمیریزیم،خب بعدش nتا صفرو حذف میکنیم و بجاش ۱ میخونیم که کلا n+1 یک خوندیم و در اخرم هر چنتا صفر که بخوایم میتونیم بخونیم چون اون رشته ی تولیدی صدرصد با اون زبان اولمون متفاوت میشه...
یادت باشه شما نمیتونی با یه عبارت منظم همه رشتهایی که مکمل یه زبان تولید میکنه رو نشون بدی،
ولی کلا میتونی بگی
Zigma Star - L1 = L'
اگه خواص مجموعها یادت باشه، اینم همون مثلا شما نمیتونی بگی مکمل مجموعه ۱،۲،۳، نسبت به مجوعه جهانی چی میشه
Sent from my GT-N5100 using Tapatalk HD

RE: زبان های مستقل از متن [tex]0^n1^n0^n[/tex] - majidfathi69 - 27 دى ۱۳۹۲ ۰۱:۳۸ ق.ظ

مکمل این زبان مگه زبانی نمیشه که کلیه رشته های سیگما استارو تولید کنه به جز رشته های این زبان؟

Sent from my C6903 using Tapatalk

RE: زبان های مستقل از متن [tex]0^n1^n0^n[/tex] - 1-1 - 28 دى ۱۳۹۲ ۰۲:۴۴ ب.ظ

(۲۷ دى ۱۳۹۲ ۰۱:۳۸ ق.ظ)majidfathi69 نوشته شده توسط:  مکمل این زبان مگه زبانی نمیشه که کلیه رشته های سیگما استارو تولید کنه به جز رشته های این زبان؟

Sent from my C6903 using Tapatalk

این زبان چه جوری مستقل از متن شده؟ یکی توضیح می ده؟

Re: RE: زبان های مستقل از متن [tex]0^n1^n0^n[/tex] - majidfathi69 - 04 بهمن ۱۳۹۲ ۱۲:۱۹ ق.ظ

همون طور که دوستان اشاره کردند قسمتی از مکمل زبان مورد نظر بصورت زیر است
مکملش رو میشه از اجتماع این ۳ زبان به دست آورد:(L1)
۱- صفرهای دو طرف برابر نباشه.
۲- تعداد صفرهای سمت چپ با ۱ها برابر نباشه.
۳- تعداد صفرهای سمت راست با ۱ها برابر نباشه.

علاوه براین زبانی که رشته هایی تولید میکند که زیر رشته ۱۰۱ را در رشته های خود دارد. (L2)
اجتماع دو زبان L1 و L2 مکمل زبان مورد نظر میباشد.
البته L2 منظم میباشد و L1 مستقل از متن میباشد. که در این مورد اجتماع هم مستقل از متن میباشد.

Sent from my C6903 using Tapatalk