صفحه‌ها: ۱ ۲
دوستان میشه توضیح بدید که گرامر روبرو زبانش منظم است یا نامنظم؟(لطفا با توضیح)
این سوال کنکور ۸۷ علوم کامپیوتره که کتاب پارسه فقط به دلیل اینکه گرامر از لحاظ ظاهری که در سوال آمده گرامر نامنظم است زبان را نامنظم فرض کرده در صورتی که به صرف نوشتن یک گرامر نامنظم برای زبانی آن زبان که نامنظم نیست درسته؟
با عرض پوزش خود گرامر را یادم رفت ذکر کنم
S->0S1|1S0|AA
A->0A|λ
A->A1|λ
(۲۱ آذر ۱۳۹۱ ۱۰:۱۱ ق.ظ)lestarlight نوشته شده توسط: دوستان میشه توضیح بدید که گرامر روبرو زبانش منظم است یا نامنظم؟(لطفا با توضیح)
این سوال کنکور ۸۷ علوم کامپیوتره که کتاب پارسه فقط به دلیل اینکه گرامر از لحاظ ظاهری که در سوال آمده گرامر نامنظم است زبان را نامنظم فرض کرده در صورتی که به صرف نوشتن یک گرامر نامنظم برای زبانی آن زبان که نامنظم نیست درسته؟
با عرض پوزش خود گرامر را یادم رفت ذکر کنم
S->0S1|1S0|AA
A->0A|λ
A->A1|λ
زبانش میشه w 0n 1m 0k 1h wr که چون w و wr مستقل از متنه و اون جمله وسطی منظمه تنها درصورتی میتونیم بگیم این زبان منظمه که بتونیم به نوعی این w , wr رو بپوشانیم یا در حقیقت اون جمله وسطی بتونه w , wr رو بخوره و ناپدیدش کنه که اگه یه چنتا رشته بهش بدیم میبینیم که نمی تونه این کارو بکنه.
مثلاً به ازای w=01101
با سلام
زبانی منظمه که گرامرش منظم باشه.گرامری منظمه که قوانینش صرفاً خطی راست یا قوانینش صرفاً خطی چپ باشه.
این گرامر قوانینش هم خطی راسته [tex]A \rightarrow 0A[/tex] هم خطی چپه [tex]A \rightarrow A1[/tex]، لذا منظم نیست.
(۲۱ آذر ۱۳۹۱ ۱۰:۱۱ ق.ظ)lestarlight نوشته شده توسط: S->0S1|1S0|AAبه نظر من هم منظمه.این گرامر زیان زیررو تولید میکنه:
A->0A|λ
A->A1|λ
*(*۱+*۰) هست که یک زیان منظمه . قانون اول شک برانگیزه ولی چون این گرامر اونها رو هم پوشش میده پس مشکلی بوجود نمیاد. همچنین قانون دوم و سوم رو هم میشه اصلاح و هردورو تبدیل به خطی راست یا چپ کرد طوریکه به رشته های تولید شده اشکلی وارد نکنه.
سلام. بنظر من که منظم نیست. نمیشه یه گرامر منظم برای [tex]1^n01010^n[/tex] نوشت. مستقل از متنه.
(۲۷ آذر ۱۳۹۱ ۱۲:۰۱ ق.ظ)Jooybari نوشته شده توسط: سلام. بنظر من که منظم نیست. نمیشه یه گرامر منظم برای [tex]1^n01010^n[/tex] نوشت. مستقل از متنه.ولی رشته هایی با همون مشخصاتی که ذکر کردید ([tex]1^n01010^n[/tex] ) رو میتونه تولید کنه
بنظر من یه نکته هست بعضی زبانها منظم گرامر منظم ندارند ولی زبانشون منظم هست اینم گرامر منظم شاید نشه براش نوشت ولی زبانش منظمه!
(۲۷ آذر ۱۳۹۱ ۱۲:۴۴ ق.ظ)fatima1537 نوشته شده توسط:(27 آذر ۱۳۹۱ ۱۲:۰۱ ق.ظ)Jooybari نوشته شده توسط: سلام. بنظر من که منظم نیست. نمیشه یه گرامر منظم برای [tex]1^n01010^n[/tex] نوشت. مستقل از متنه.ولی رشته هایی با همون مشخصاتی که ذکر کردید ([tex]1^n01010^n[/tex] ) رو میتونه تولید کنه
و همچنین نباید [tex]1^n01010^{n 1}[/tex] رو تولید کنه. رشته های این زبان فقط بفرم [tex]w0^m1^n0^p1^qw^R ; w\in\{0,1\}^* , m,n,p,q\geq 0[/tex] هستن. احتمالاً S->AA رو با S->SS اشتباه گرفتید.
(۲۷ آذر ۱۳۹۱ ۰۱:۰۲ ق.ظ)teacherpc نوشته شده توسط: بنظر من یه نکته هست بعضی زبانها منظم گرامر منظم ندارند ولی زبانشون منظم هست اینم گرامر منظم شاید نشه براش نوشت ولی زبانش منظمه!
برای زبانهای منظم میشه گرامر منظم نوشت.
(۲۷ آذر ۱۳۹۱ ۰۷:۴۸ ب.ظ)Jooybari نوشته شده توسط: و همچنین نباید [tex]1^n01010^{n 1}[/tex] رو تولید کنه. رشته های این زبان فقط بفرم [tex]w0^m1^n0^p1^qw^R ; w\in \{0,1\}^* , m,n,p,q\geq 0[/tex] هستن. احتمالاً S->AA رو با S->SS اشتباه گرفتید.تشکر از شما . بله به نظرم اومد که شبیه هم رفتار میکنند . درسته که در S->SS نقطه شروع به صورت بازگشتی تکرار میشه ولی در S->AA و a->0a و a->1a هم این مورد هست.یه سئوال برام پیش اومده.فرق بین s->aa و s->ss چیه؟
s->ss برای ساخت گرامری که مثلا با a شروع شود و با a تموم بشه و با bb وسطشون باشه...به مثالم نیگاه...(البته اگه منظورتون رو درست فهمیده باشم)
s->asb
s->bsa
s->landa
حالا اگه من بخام اون چیزی رو که میخام بسازم یعنی abba رو ..آیا میتونم با گرامر بالا بسازم؟جواب مسلما نه هست
پس باید قاعده ی s->ss رو هم با گرامر اضافه کنم...
(۲۸ آذر ۱۳۹۱ ۱۲:۴۱ ق.ظ)jameshenas نوشته شده توسط: s->ss برای ساخت گرامری که مثلا با a شروع شود و با a تموم بشه و با bb وسطشون باشه...به مثالم نیگاه...(البته اگه منظورتون رو درست فهمیده باشم)ممنون از جوابتون ولی منظور من تفاوت بین S->SS و S->AA هست
s->asb
s->bsa
s->landa
حالا اگه من بخام اون چیزی رو که میخام بسازم یعنی abba رو ..آیا میتونم با گرامر بالا بسازم؟جواب مسلما نه هست
پس باید قاعده ی s->ss رو هم با گرامر اضافه کنم...
(۲۱ آذر ۱۳۹۱ ۰۲:۴۸ ب.ظ)hp1361 نوشته شده توسط: با سلامموافقم
زبانی منظمه که گرامرش منظم باشه.گرامری منظمه که قوانینش صرفاً خطی راست یا قوانینش صرفاً خطی چپ باشه.
این گرامر قوانینش هم خطی راسته [tex]A \rightarrow 0A[/tex] هم خطی چپه [tex]A \rightarrow A1[/tex]، لذا منظم نیست.
(۲۸ آذر ۱۳۹۱ ۱۲:۵۵ ق.ظ)fatima1537 نوشته شده توسط:(28 آذر ۱۳۹۱ ۱۲:۴۱ ق.ظ)jameshenas نوشته شده توسط: s->ss برای ساخت گرامری که مثلا با a شروع شود و با a تموم بشه و با bb وسطشون باشه...به مثالم نیگاه...(البته اگه منظورتون رو درست فهمیده باشم)ممنون از جوابتون ولی منظور من تفاوت بین S->SS و S->AA هست
s->asb
s->bsa
s->landa
حالا اگه من بخام اون چیزی رو که میخام بسازم یعنی abba رو ..آیا میتونم با گرامر بالا بسازم؟جواب مسلما نه هست
پس باید قاعده ی s->ss رو هم با گرامر اضافه کنم...
بنظرم نمیشه تو aa کنترل داشته باشیم..ولی تو ss رشته ها برابر تولید میشن یعنی منظمه تولید میشه... ولی با aa قاطی به پاتیه...(چی نوشتم ها..)
ولی مشکل داره این قواعد بقول دوستمون هم از راست و هم از چپ تولید میشه...
(۲۸ آذر ۱۳۹۱ ۱۲:۲۷ ق.ظ)fatima1537 نوشته شده توسط: فرق بین s->aa و s->ss چیه؟
S->SS گرامر رو خیلی گسترش میده و به عبارت منظم شما که همون سیکما استاره میرسه:
S->SS->SSS->SSSS->... و اگه به A بریم سیکما استار تولید میشه. ولی اگه S->AA فقط داشته باشیم:
S->AA و چون *A->a*b رو فقط داریم رشته های تولیدی محدودتره.
نقل قول: منظور من تفاوت بین S->SS و S->AA هستفرق اساسی این دو تا در این هست s->ss تنوع خیلی بیشتری نسبت به aa به ما میده و زبان های بیشتری رو قبول میکنه در حقیقت مثه * عمل میکنه البته به جای ss میشود تمام جملاتی رو که در سمت راست s هستند رو به آخرشان s اضافه کنیم که همون ss میشوند سوال گرامر ارشد ۹۱ هم مینطوری بود
البته به شرطیکه دیگه A متغیر بازگشتی دوباره به s نداشته باشه که دیگه به قطعیت نمیشه اینطوری گفت. حالا سوالو نگاه کنید می بینید aA محدود شده به این که بین ab یا ba قرار بگیره در صورتیکه ss این محدودیت رو بر میداره و رشته ای مثه این رشته رو تولید میکنه aaab baaaa که فاصله بینشان برای اینکه بگم این دو تا s هست که شده این.
متوجه شدم.خیلی ممنون از توضیحات همه شما
درواقع با قانون s->ss میتونیم دوباره به حالت شروع برگردیم و بازهم بسطهای مشابه ss را تولید کنیم(مثلا ss و ssss وssssss)
ولی با s->aa دیگه نمیتونیم به s برگردیم و مجبوریم قوانین بعدی را بسط دهیم(a->0aوa->a1).که قوانین بعدی هم تولید کننده یک زبان منظم هستند.