گرامر زیر چه زبانی تولید می کند؟
S→ABS|ab
A→aA|a
B→bB|b

خیلی راحته
فکر کن میخایی بازی مار پله کنی قانون اینه که از خونه ۱ بازی شروع میشه تا بخونه پایان برسی
زبان محاوره ما قواعدی داره که ما وقتی میخاییم حرف بزنیم از اونا استفاده میکنیم
اینجا یک گرامر هست که به ما میگه چطور کلمات زبان رو تولید کنیم یادت باشه چطور!
ما باید از متغیر شروع عملیات ایجاد کلمه ای از زبان(اصطلاحن میگیم رشته ای از زبان) رو شروع کنیم که معمولن متغیر شروع رو با S نشون میدیم
فلش ها به ایم معنی هست که شما حق داری سمت عبارت سمت چپ هر قانون رو با یکی از عبارات سمت راست که بوسیله خط | جداشدند جایگزین کنی
پس قانون اول به من میگه میتونی از S به ABS یا ab بری (به عبارت دیگر میگه میتونی متغیر S را با عبارت ABS یا ab جایگزین کنی) خب توجه کن متغیرهای با حروف بزرگ همیشه را غیر پایانی و متغیر های کوچیک رو عناصر پایانی میگیم
خب چند تا تمرین
عبارت ab چطور تو سط گرامر فوق تولید میشود؟
پاسخ : کافی است S را با ab جایگزین کنیمS→ab
سوال دوم )ایا رشته aabab عضو زبان گرامر فوق است؟
پاسخ ) از متغیر شروع گرامر (در اینجا S) شروع کرده و سعی میکنیم با جایگزینی درست و استفاده صحیح از قواعد گرامر
رشته aabab را تولید کنید اگه موفق نشیم این رشته را با جایگزینی ایجاد کنیم میگیم این رشته متعلق به گرامر ما نیست.
خب
به رشته نگاه میکنیم سمت چپش با a شروع میشه
پس باید از قاعده هایی استفاده کنیم که با میشن یا یجوری میتونن a تولید کنن
من با شروع از S دو انتخاب دارم که انتخاب ab اینجا بدرد ما نمیخوره S→ABS خب در مرحله بعدی ما سه متغیر داریم
A و B و S که میتونیم جایگزین کنیم ما باید چپ ترین متغیر رو جایگزین کنیم که اینجا سمت چپترین A هست
Aطبق گرامر میتونه با دو عبارت جایگزین بشه ما نگاه میکنیم به رشته میبینیم که دوتا a داره و طبق گرامر تنها متغیر Aمیتونه a تولید کنه پس من باید از قاعده A→aA اسفاده کنم
تا انجا ببینیم چی ساختیم aABS خب ما عبارت خودمون رو با رشته مقایسه میکنیم میبینیم که شبیه هستن ولی رشته دوتا a داره که ما یکیش رو ایجاد کردیم و یک a دیگه میخاد ببینیم چه باید کرد
سمت چپ ترین متغیر عبارت aABS متغیر Aهست که اگه من از قاعده A→a استفاده کنم عبارت aaBS تولید خواهد شد
باز به رشته نگاه میکنیم و به عبارت خودمون میبینیم یک b بعد از aa داره حالا سمت چپ ترین متغیر یعنی B را با b جایگزین کن B→b تا به تولید رشته aabab نزدیکتر شویم خب یک ab در انتهای رشته هست که ما نساختیمش
ما یک متغیر S داریم حالا اگه گفتی در عبارت aabS باید S را با چه عیارتی جایگزین کنیم تا به رشته aabab برسیم؟
پاسخ راحته S→ab در اینجا بازی تمام شد و شما بازی رو به پایان رسوندی و چون موفق شدی با شزوع از متغیر شروع گرامر(یعنیS) و با کمک گرامر رشته رو ایجاد کنی پس نتیجه میگیری این رشته عضو زبان گرامر ما هست!
حالا یک سوال دیگه (زبان گرامر فوق چیست؟) و چطور میشه زبان این گرامر را پیدا کرد؟
سوال دوم این گرامر جز کدام دسته زبانها هست؟(منظم؟ مستقل از متن ؟...)
سوال سوم) درخت اشتقاق گرامر فوق رو رسم کنید؟
سوال چهارم) گراف اشتقاق گرامر فوق رو رسم کن؟
سوال پنجم)ایا گرامر فوق بازگشتی چپ داره؟

دوستان عزیز چون جواب نوشتین منتقل میشه ولی عدم رعایت نظم انجمن منجر به حذف سوال و جواب میشه. لطفا" رعایت فرمایید.

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.


مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.


مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

با سلام بر دوستان عزیز و مدیرکل : با عرض پوزش که اینجا پست دادم : حواسم نبود: لطفا حذف نکنید!!
جنابnasi1391 :شما لطف کن ادامه مطلب را توضیح بده؟ سپاس
راستی چند تا سئوال در مورد گرامر های مستقل و وابسته به متن داشتم که بعدا مطرح می کنم

باتشکر از تمام اعضا

(۰۴ آذر ۱۳۹۱ ۰۳:۱۸ ب.ظ)jafar.sh نوشته شده توسط:  با سلام بر دوستان عزیز و مدیرکل : با عرض پوزش که اینجا پست دادم : حواسم نبود: لطفا حذف نکنید!!
جنابnasi1391 :شما لطف کن ادامه مطلب را توضیح بده؟ سپاس
راستی چند تا سئوال در مورد گرامر های مستقل و وابسته به متن داشتم که بعدا مطرح می کنم

باتشکر از تمام اعضا

ببین دوست عزیز : ما تو این گرامر یه قاعده داریم به این شکل : [tex]A \to aA\mid a[/tex] این قاعده یه جورایی مثل پنگوئن میمونه !
اسم پنگوئن ما هست [tex]A[/tex] این خانم پنگوئن ما میتونه یه دونه بچه به دنیا بیاره (منظورم a ) و از دنیا بره و یا اینکه میتونه یه بچه به دنیا بیاره و خودشم کنارش باشه (منظورم ّaA) تا اینجا اوکی ؟ خوب ... پس کار این قاعده به دنیا آوردن بچه است (منظور از بچه کاراکتر a است ) حالا میتونه یه بچه به دنیا بیاره میتونه nتا بچه به دنیا بیاره (به شکل شماره یک که پیوست کردم نگاه کن)
خوب به همین ترتیب قاعده [tex]B \to bB\mid b[/tex] همنطور ولی بجاش b به دنیا میاره.
در جریانی که ما باید با S شروع کنیم. اوکی ؟ خوب حالا بجای S من چی بزارم ؟ مجبورم یا بزارم ab که اگه بزارم دیگه کارتمومه چون a و b جفتشون بچه هستن و نمیتونن بچه بدنیا بیارن و کار خلاصه !!! ولی اگر بیام بجای S بزارم ABS به این نتیجه میرسم که تونستم هم خانم پنگوئن A و هم B رو به وجود بیارم که اونا هم واسم باید بچه به دنیا بیارن (حداقل یکی) ... خوب پس اینجوری نتیجه میگیرم که اگر از S رفتم به ABS میتونم به جای A و B چنین بنویسم که [tex]a^nb^mS[/tex] این جمله یعنی متغییر A (خانم پنگوئن A) میتونه واسم n تا بچه بیاره (البته [tex]n\geq 1[/tex] و خانم پنگوئن B میتونه واسم m بچه بیاره (البته [tex]m\geq 1[/tex]) البته دقت کن که تعداد بچه های خانم پنگوئن A ربطی به تعداد بچه های پنگوئن B نداره به همین دلیل یکی رو n و یکی رو m گذاشتیم.
خوب تا اینجا که حله و رسیدیم به [tex]a^nb^mS[/tex] حالا بجای S چی بزاریم ؟ انگار یه جورایی دوبار ماجرا از اول ! ما دوساعت تحلیل و پنگوئن بازی کردیم دوباره رسیدم به S !!! خوب مشکلی نیست که به جای S دوباره همین ماجرا ها رو از اول قرار میدیم .... و میرسیم به این که [tex]a^nb^ma^yb^zS[/tex] ای بابا ! دوباره ْS به دنیا اومد که ! چه کار کنیم این S از بین بره ؟ خوب راهی نداریم بجز اینکه به جای S بزاریم ab و شکل کلی زبان ما میشود : [tex]a^nb^ma^yb^z .... ab[/tex] یعنی این گرامر ما رشته هایی رو تولید میکنه که حتمآ تهشون ab هست خوب این جوری که من نوشتم [tex]a^nb^ma^yb^z .... ab[/tex] یکم نامتعارفه معمولآ تو این درس اینجوری مینویسن [tex](a^nb^m)^ ab[/tex] شاید سوال پیش بیاد که + یعنی چی ؟ + اینجا به این معنی که حتما یکبار به خانم پنگوئن A و B باید سر بزنی.
سعی کردم آسون بگم ببخشید اگه یه جاهایی تند رفتم.

متشکر دوست عزیز:ان عکسی که گذاشتید درخت اشتقاق هست!!؟؟؟ چرا اینقدر بی کیفیت هست(چیزی معلوم نیست داخلش!)؟؟؟ گمان کنم ادم با توضیح درختی بهتر بفهمه!

کسی میدونه این عبارت زیرین یعنی چی؟؟؟

سپاس

(۰۴ آذر ۱۳۹۱ ۰۸:۲۲ ب.ظ)jafar.sh نوشته شده توسط:  متشکر دوست عزیز:ان عکسی که گذاشتید درخت اشتقاق هست!!؟؟؟ چرا اینقدر بی کیفیت هست(چیزی معلوم نیست داخلش!)؟؟؟ گمان کنم ادم با توضیح درختی بهتر بفهمه!

کسی میدونه این عبارت زیرین یعنی چی؟؟؟

سپاس

ای بابا کیفیتش خوب بود که ! آره درخت اشتقاق بود. بیخیال، بیا از اینجا دانلودش کن :

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

در ضمن [tex](a^nb^m)^ ab[/tex] یعنی این که : میتوانی به تعداد دلخواه از محتویات داخل پرانتز استفاده کنی ولی حداقل یکبار باید استفاده کنی شاید بگی نفهمیدم باشه آسون تر میگم.
من اگر چنین زبانی رو بنویسم [tex]L=(a)^ [/tex] این زبان یعنی اینکه : از داخل پرانتز میتوانی به تعداد یکبار یا بیشتر استفاده کنی
مثلآ اگر یکبار استفاده کنی میتوانی رشته a رو بسازی ولی اگر دو بار استفاده کنی میتوانی رشته aa رو بسازی و الی آخر ...
خوب حله ؟ + یعنی استفاده یکبار یا بیشتر
مثلا اگر چنین زبانی داشتیم : [tex]L=(ab)^ [/tex] میتونیم این رشته ها رو باهاش بسازیم :
ab,abab,ababab,abababab,.... اوکی ؟
حالا اگر داشتیم [tex]L=(ab)^ c[/tex] میتوانیم این رشته ها رو بسازیم :
abc,ababc,abababc,ababababc,.... حله ؟
خوب اگر داشتبه باشیم زبانی بدی شکل : [tex]L=(a^nb^m)^ ab[/tex] و برای راحتی و فهم بیشتر n, m رو بگیریم ۲ میتوانیم چنین رشته های رو ساخت :
aabbab
aabbaabbab
aabbaabbaabbab

متشکر دوست عزیز: یک چیز هایی را فهمیدم ولی....
راستی فرق + و * چی هست توی یک عبارت؟؟؟ لطفا یک مثال برنید؟
سپاس

(۰۴ آذر ۱۳۹۱ ۱۱:۵۸ ب.ظ)jafar.sh نوشته شده توسط:  متشکر دوست عزیز: یک چیز هایی را فهمیدم ولی....
راستی فرق + و * چی هست توی یک عبارت؟؟؟ لطفا یک مثال برنید؟
سپاس

قضیه اینه که روی هرچی (مثلآ هرچیزی باشه [tex]\alpha[/tex]) که ما * میزاریم بدین معنی میشه که از اون عبارت ([tex]\alpha[/tex])میتونی یا استفاده نکی یا چندین بار بطور نامتناهی استفاده کنی. فرض کن [tex]\alpha =nader[/tex]
اونوقت [tex](nader)^*[/tex] به این معنی هست که :
اگر هیچی استفاده نکنی به رشته تهی خواهی رسید. (تقریبآ همان خرزو خان )
اگر یکبار از * استفاده کنی به رشته : nader خواهی رسید
اگر دو بار استفاده کنی به رشته : nadernader خواهی رسید
اگر n بار استفاده کنی n تا nader پشت سر هم خواهی داشت
و الی آخر...
ولی فرق + با * اینه که وقتی + داری نمیتونی هیچی استفاده نکنی حتمآ باید یکبار استفاده بکنی.
مثلآ تو مثال بالا اگر بجای * میذاشتم + دیگه حق نداشتی رشته تهی رو درست کنی.

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

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

من جواب این سئوال ها را دارم ولی مفهومش را نمی فهمم زیاد !! لطفا یک توضیح کوچک بدهید دوستان!!

سپاس

جواب سوالل ۱ :
A -> epsilon | Aab
به اینطور سوال ها بازگشتی فکر کنید. باید یک جفت ab بذاریم و بهش اجازه بدیم هر چند بار دیگه که خواست این جفت رو بذاره
اگر اول کار به اپسیلون بره یعنی رشته ای تولید نکرده که مفهوم (ab) ^ 0 که تو * هست رو پوشش میده
در غیر اینصورت :
epslin
Aab
Aabab
...
Aabababab
و در نهایت A به اپسیلون میره و تولید رشته تموم میشه

سوال دوم برای من واضح نیست !

دوستان عزیز در هر تاپیک فقط یه سوال مطرح کنید.