تالار گفتمان مانشت

سلام.

از دوستانی که پاسخ سوالات زیر رو می دونند خواهشا راهنمایی نمایند چون این درس واقعا گیج کننده شده.



ممنونم.

سئوال اول:
ترتیب اتصال به همون ترتیبی هست که در عبارت اومده و من منظور این سوال را دقیق نمیدونم . و رشته هایی تولید میشه که میتونه شامل ترکیبی از 01 و 1 ها باشه ، که چون بالای پرانتز * هست پس میتونه بینهایت رشته شامل محموعه ای از 01 ها و 1 ها را تولید کنه و بعد از اون میتونه یک حرف 0 یا رشته پوچ قرار بگیره و بعد تعداد صفر یا بیشتر حرف 1 (چون علامت کلین استار هست) و بعد هم میتونه حرف 0 قرار بگیره یا رشته پوچ
برای سئوال دوم:
به نظر من معادل هم نیستند چون عبارت اول میتونه جمله 00 را تولید کنه ولی عبارت دوم نمیتونه 00 را تولید کنه
سئوال 3:
اول به تعداد دلخواه حرف aیاbتولید میشه پس از اون حتماباید یک حرف b قرار بگیره و بعد هم به تعداد دلخواه حرف a یا ab میتونه قرار بگیره
متوجه منظور سئوال نمیشم

سلام. سوال ۱ و ۲ معادلن. رشته هایی که زیررشته ۰۰ ندارن رو میپذیرن.

[tex](1^*011^*)^*[/tex] رو درنظر بگیرید. میگه مجموعه چندتا(حداقل هیچی) 01 که در فضاهای اطرافشون میتونه 1 بیاد ولی اگه 01 نداشته باشیم 1 هم نداریم. یعنی رشته های [tex]\lambda[/tex] و [tex]1^*011^*[/tex] و [tex]1^*011^*011^*[/tex] و ... تفاوتی که این عبارت با [tex](1 01)^*[/tex] داره اینه که رشته اول نمیتونه زیررشته هایی که فقط از 1 ساخته میشن رو تولید کنه. یعنی یا رشته نال رو تولید میکنه و یا رشته های بدون زیررشته 00 که حداقل یک 0 دارن. ولی عبارت دوم علاوه بر این دو حالت، میتونه رشته هایی که فقط از 1 ساخته میشن رو هم تولید کنه. یعنی [tex](1 01)^*=((1^*011^*)^* 1^*)[/tex]. آخر هردو رشته هم مشابهه. یا به نال ختم میشن و یا به 0. اگه به نال ختم بشن رشته نهایی حالتیه که رشتمون به 1 ختم بشه یا نال باشه.

سوال سوم هم تمام رشته هایی که حداقل یک b دارن رو تولید میکنه. رشته های بطول کمتر از 4 تولید شده میشه همه رشته های بطول حداکثر 4 که حداقل یک b راشته باشن.

سوال چهار هم منظور از رشته های پیچیده رو نمیفهمم. اگه منظورش همین پرانتزهای پشت سر همه که باید هر پرانتز رشته خودشو مشخص کنه و ترتیبش از چپ به راسته.

از هر دو شما عزیزان سپاسگزارم.

در مورد سوال 1 و 2 هر دو عبارات معادل هم هستند (مثال کتاب لینز هستش).

1. منظورم از ترتیب اتصال هم، این هستش که، این عباراتی که در بالا گفتم رو هریک رو چطوری و از کجا باید
ضرب در هم کرد، تا به هم متصل شوند و رشته رو تولید کنند.

مثلا در سوال سه ترتیب و تقدم ضرب رو از چپ بگیریم اول باید *(a+b) رو از توان صفر و یک و ... تشکیل بدهیم
و بعد با {b} اتصال بدهیم و رشته تولیدی این دو رو هم با *(a+ab) در هم ضرب کنیم تا رشته کامل تولید بشه؟
درسته؟

2. سوال دیگرم هم این هستش که: در سوالات بالا اگر به جای ستاره، + داشتیم فقط مورد لاندا در رشته های تولیدی
ایجاد نخواهد شد؟درسته؟

3. یک سوال دیگر هم دارم: ترتیب اتصال از چپ به راست هستش و اینکه اولویت و حق تقدم پرانتز بیشتر از ستاره، + و اتصال هستش؟ درسته؟

ببخشید سوالاتم زیاد شد.من توی این درس کاملا مبتدی هستم.

ممنونم.

اولویتی برای ترتیب وجود نداره. از هر پرانتز یه مقدار انتخاب میشه و بعد عبارات پشت سر هم قرار میگیرن. این ترتیبی که میگید رو از راست هم میتونید اعمال کنید. مشکلی پیش نمیاد. عبارات منظم ترتیب انتخاب ندارن. هر پرانتزو میشه یه زیرnfa گرفت و این زیرnfaهای تولید شده رو میشه به همین ترتیب با نال به هم وصل کرد. حالت شروع و نهایی رو که اضافه کنید nfa کلی زبان تولید میشه. کاری نداریم کدوم زودتر از بقیه اومده. هرقسمت از عبارت یه بخشی از nfa میشه که از بخشهای دیگه قابل جداشدنه.
فرق * و + هم فقط توی لانداست. + یعنی حداقل یکی انتخاب بشه و * این حداقل رو نداره و میشه انتخاب نکرد.
بیشترین اولویت رو پرانتز داره. * و + هم روی یک سمبل یا پرانتز اعمال میشه. ضرب هم اولویت بعدیه.

من 1 سئوال دارم. در عبارت اول جمله 00 قابل تولید هست ولی در عبارت دوم امکان تولید 00 نیست ولی چطور میشه گفت معادلند؟

فکر کنم سوال شما بخاطر + بین دو عبارت [tex](1^*011^*)^*(0 \lambda)[/tex] و [tex]1^*(0 \lambda)[/tex] باشه. یعنی یکی از این دو عبارت انخاب میشه. شما با ضربشون اشتباه گرفتید.

ممنون.نه من اصلا متوجه این علامت جمع ( که انتخاب یکی از دو رشته است) نبودم

سلام مجدد و اینکه از هر دو شما عزیزان سپاسگزارم.

یک سوال دیگر هم دارم:



ممنونم.

بله.با هم برابرند:
[tex](a b)(a b)^{*}\equiv (a b)^{ }[/tex]

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

[tex](1 01)^{*}[/tex]
این چه رشته هایی رو تولید می کنه می شه مثال بزنید؟
---------------

[tex](1 10)^{*}[/tex]
این چه رشته هایی رو تولید می کنه می شه مثال بزنید؟
---------------

[tex](0 1)^{*}[/tex]

فرق هر سه اینها در چیه؟
--------------

چرا وقتی گفته می شه تمامی رشته هایی که حداقل یک ۰۰ دارند از این [tex](0 1)^{*}[/tex] در جواب به کار می ره. در صورتی که وقتی گفته می شه تمامی رشته هایی که ۰۰ ندارند یا دقیقا یک ۰۰ یا دقیقا دو ۰۰ دارند از اینها [tex](1 10)^{*}[/tex] و[tex](1 01)^{*}[/tex] در جواب استفاده می شه چرا در جوابشون نمی توان مثل همون حداقل ۰۰ از این [tex](0 1)^{*}[/tex] استفاده کرد.

ممنونم.

1:
رشته هایی که در انتهای اونها صفر قرار نمیگیره و هیچ دو صفری هم در کنار هم قرار نمیگیرند
2:
شبیه بالایی است ولی: رشته هایی که در انتهای اونها یک قرار نمیگیره و هیچ دو تا صفری در کنار هم قرار نمیگیرند
3:
سیگما استار رو تولید میکنه(یعنی هر ترکیب دلخواه و قابل تصوری از صفر و یکها)
فرق 1و2 با 3 در اینه که 1و 2 در آخرین حرف و همچنین محل قرار گیری صفر و یکها محدودیت دارند ولی 3 هیچ محدودیتی نداره

(30 خرداد 1391 08:07 ب.ظ)Prim$ نوشته شده توسط: [ -> ]چرا وقتی گفته می شه تمامی رشته هایی که حداقل یک ۰۰ دارند از این [tex](0 1)^{*}[/tex] در جواب به کار می ره. در صورتی که وقتی گفته می شه تمامی رشته هایی که ۰۰ ندارند یا دقیقا یک ۰۰ یا دقیقا دو ۰۰ دارند از اینها [tex](1 10)^{*}[/tex] و[tex](1 01)^{*}[/tex] در جواب استفاده می شه چرا در جوابشون نمی توان مثل همون حداقل ۰۰ از این [tex](0 1)^{*}[/tex] استفاده کرد.

چون زبان 1 و 2 نمیتونه 2 تا صفر در کنار هم تولید کنه(به خاطر 01 که در این گرامر هست) ولی زبان *( 1+ 0) میتونه
درواقع در هر بار تولید رشته(وقتی که توی پرانتز علامت+هست)فقط یکی از عبارات موجود در پرانتز میتونند استفاده بشن.

خیلی خیلی ممنونم از پاسخگوییتون.
ببخشید سوالاتم زیاد شده چون بنده مبتدی هستم.

---------------------
آیا جواب زیر درست هست:
تمام رشته هایی که شامل دقیقا(حداکثر) یک aa هستند؟

[tex](b ab)^{*}aa(b ba)^{*}[/tex]

---------------------
در مورد سوال : تمام رشته هایی که 00 ندارند؟

[tex](1 01)^{*}(\lambda 0)[/tex]

چرا انتهای جواب رو [tex](\lambda 0)[/tex] می نویسیم، اگر خالی هم بذاریم باز هم
00 تولید نخواهد شد پس چه لزومی داره [tex](\lambda 0)[/tex] بنویسیم؟

---------------------
ممنونم.

سوال اولتون برای دقیقاً درسته. اگه حداکثر رو میخواست باید بجای aa مینوشتید (aa+lambda) که یکیشون انتخاب بشه.

سوال دومتون درسته بدون پرانتز آخری هیچ رشته ای شامل 00 رو قبول نمیکنه ولی همه رشته هایی که 00 ندارن تولید نمیشه. فقط رشته هایی که به 1 ختم میشن تولید میشن. مثلاً 110110 تولید نمیشه.

ازتون خیلی خیلی ممنونم.

برای چی توی حداکثر باید لاندا رو هم گذاشت؟
حداکثر و دقیقا چه تفاوتی با هم دارند؟

ممنونم.