$(ab)^ a^* \lambda$

(۰۵ آذر ۱۳۹۱ ۰۹:۳۴ ب.ظ)jafar.sh نوشته شده توسط:  با سلام بر دوستان عزیز

من ۲ تا سئوال داشتم در مورد گرامر ها: لطفا به صورت خیلی ابتدائی و ساده توضیح بدید؟؟؟

سئوال ۱
گرامر مستقل از متنی بنویسید که زبان *(ab) را تولید کند؟؟

سئوال ۲
برای زبان زیر یک گرامر بنویسید؟؟
L=((ab)^+) a^*+ landa

هر کدام را که بلد بودید لطفا به صورت صفر کیلومتری راهنمایی کنید؟
در ضمن اگر جای بدی تایپیک زدم:به من بگید که دقیقا کجا باید سئوالم را مطرح کنم(لینک بدید!)

سپاس

سوال شماره دوم شما اینه ؟
$(ab)^ a^* \lambda$

بله:هیمنه:لطفا یکم ساده توضیح بده!!
سپاس

(۰۵ آذر ۱۳۹۱ ۰۹:۳۴ ب.ظ)jafar.sh نوشته شده توسط:  با سلام بر دوستان عزیز

من ۲ تا سئوال داشتم در مورد گرامر ها: لطفا به صورت خیلی ابتدائی و ساده توضیح بدید؟؟؟

سئوال ۱
گرامر مستقل از متنی بنویسید که زبان *(ab) را تولید کند؟؟

سئوال ۲
برای زبان زیر یک گرامر بنویسید؟؟
L=((ab)^+) a^*+ landa

هر کدام را که بلد بودید لطفا به صورت صفر کیلومتری راهنمایی کنید؟
در ضمن اگر جای بدی تایپیک زدم:به من بگید که دقیقا کجا باید سئوالم را مطرح کنم(لینک بدید!)

سپاس

ببینید خیلی ساده اند!
سوال اول باید به تعداد نا مشخص ab رو تولید کنه!
پس مینویسیم $S\rightarrow Sab$ این یعنی اینکه هر بار یه ab به تعداد نا مشخص تکرار کن!
S سمت چپ برای ایجاد حلقه است!
و از اونجایی که به دلیل وجود استار میشه رشته تهی هم داشت پس یه قانون $S\rightarrow \lambda$ هم اضافه میکنیم که در کل میشه :
$S\rightarrow Sab | \lambda$


و اما سوال دوم :

خوب حالا واسه گرامر ما باید ۲ فاز جدا داشته باشیم که یکی abها رو تولید کنه و یکی هم aها رو(که هر دو اینها به تعداد نا مشخصند فقط abها نمیتونن خالی باشند) برای اینکار مینویسیم $S\rightarrow AB|\lambda$ که در واقع A و B دو فاز فوق الذکرند .
حالا قسمت A (به دلیل اون که اولین قسمت رو تولید میکنه باید $(ab)^$ رو تولید کنه که دقیقا همون سوال اوله با این تفاوت که S رو با A جایگذین میکنیم و به جای لامبدا ab قرار میدیم یعنی : $A\rightarrow Aab |ab$.
حالا میریم سراغ قسمت B که باید $a^*$ رو تولید کنه اینم شبیه قسمت A است فقط به جای ab باید a خالی رو بذاریم چون a به تعداد نا مشخص تکرار میشه پ اینم میشه : $B\rightarrow Ba | \lambda$
که در کل گرامر میشه :
$S\rightarrow AB|\lambda$
$A\rightarrow Aab |ab$
$B\rightarrow Ba | \lambda$

متشکر دوست عزیز: من جواب این سوال هایی را که گذاشتم را دارم: یکم جواب ها مغایرت دارند!! دوستان دیگر اگه نظری دارند لطف کنند بگویند!
در ضمن من کتاب سودکمپ را دارم ولی خیلی بد توضیح داده و چیزی نمی فهمم!!
ایا شما کتابی دیده ای که روان و ساده همه چیز هایی را که گفته اید: مثل گفتار شما گفته باشد!!!
سپاس

دوستان لطفا تصحیح بفرمائید جواب غلط را!!!

با سلام بر دوستان عزیز: من دوباره بازگشتم
یک سئوال خیلی ساده برای شما دوستان!!
فرق *(a+b) با +(a+b) چی هست؟؟
فرق بین $a^{ }b^{ }$
و $a^{*}b^{*}$
چی هست؟؟

سپاس

*(a+b) میتونه هیچی تولید نکنه اما +(a+b) حداقل باید یا یک a یا یک b تولید کرده باشه(دیگه بعد از این شرط هر تعداد a و b با هر ترتیبی میتونن بیان).

اما *a*b میتونه هر تعداد a و b ( حتی هیچی) تولید کنه که aها اول و b ها آخر باشند
+a+ b مثل قبلیه فقط حداقل باید یک ab داشته باشیم و دیگه بعد از این شرط تعداد a و b ها هر چیزی میتونه باشه(به صورت مستقل از هم یعنی تعدادشون به هم هیچ ربطی نداره)

متشکر : من یک چیز هایی فهمیدم ولی لطف کنید یک مثال عددی بزنید تا ابهام از بین بره!!
مثلا در مورد +(a+b) : ایا این عبارت میتونه ab را در کنار هم بزاره؟؟؟ یا به صورت جدا میگذارد aو b را: یعنی یا a یا b فقط!!!
یا در مورد a+b+ : ایا اگر a^2 b^2 باشد :ایا جواب aabb می شود؟؟؟
سپاس

ببینید بله کنار هم میزاره.
+(a+b) یعنی چسباندن ۱ تا بینهایت a یا b یا هر ۲ بهم بدون رعایت هیچ ترتیبی یعنی تمام شکل های ممکن که میشه a و b به هر تعداد کنار هم بچینیم اما حداقل باید یک a یا یک b رو داشته باشیم(به دلیل +)
+a+b به دو قسمت +a و +b تقسیم میشه که +a یعنی هر تعداد a از یک تا بینهایت و +b هم به همین صورت برای b هاست که این مثال برعکس قبلی ترتیبی باید رعایت شه اونم اینه که تمام a ها باید قبل از b ها بیاد.
ببین در کل هر جا + یا * بود عبارتی که زیر قلمرو این علامت هست رو بدون توجه به این که دفعه قبلی چه چیزی رو تولید کرده میتونی تولید کنی مثلا *(a+ab+bb) میتونی به هر تعداد که لازم بود a , ab ,bb رو به هر تعداد که لازم باشه استفاده کنی. مثلا تمام رشته های زیر میتونه با این عبارت منظم تولید بشه :
(فاصله بین هر زیر رشته واسه اینه که بهتر متوجه شی که کدوم انتخاب شدن)
a a a a a a
ab bb bb bb ab
a bb ab bb a a a bb ab
و هر شکلی از که از تر کیب a و ab و bb بشه تولید کرد جزء این زبانه!

متشکر دوست عزیز: حالا اگه به این صورت باشه چی ؟؟؟
$(\left ( a b \right )\left ( a b \right ))^{2} \rightarrow or\rightarrow *$

منظورت اینه که یا ۲ یا *؟
اگه اینطوره از اونجایی که ۲ زیر مجموعه * هست پس ۲ رو در نظر نمیگیریم.
حالا چون a+b ها ۲تا هستند و به ازای هر کدوم باید حتما یک a یا یک b در نظر بگیریم.
از اونجا گه * بالاشونه میشه لاندا رو هم پذیرفت.
پس در کل این عبارت تمام ترکیب های زوج از a و b رو میپذیره مثلا رشته های زیر همه مال این زبانند :
لاندا
aa bb aa
ab ab ba aa
ba bb bb bb bb
و کلا هر ترکیبی که تعداد کل زوج باشه دیگه!

اگه منظورتون چیز دیگه ایه روشن کنید اگه بدونم کمک میکنم!

متشکر : منظور من این بود که روی ان عبارت داخل پرانتز یا ۲ باشد یا * ؟؟؟ فرقی نداره کدام باشد یعنی هر کدامش را جدا تست کنیم !!!

ببینید اگه ۲ باشه رشته هایی که دقیقا ۲ بار عبارت داخل پرانتز رو داخل خودش داشته باشه
حالا عبارت داخل پرانتز میگه انتخاب یک a یا یک b و دوباره انتخاب یک a یا یک b که در کل میشه رشته های با طول فقط چهار که از هر ترکیبی از a, b ساخته شده باشند.
یعنی مثلا :
aaaa
bbbb
abab
baba
bbba
abba
و ...
حالا اگه * بود عبارت داخل پرانتز از صفر یا بیشتر بار باید تکرار شه که میشه همونی که تو پست قبلی توضیح دادم.