(۲۱ آذر ۱۳۹۱ ۱۰:۱۱ ق.ظ)lestarlight نوشته شده توسط:  دوستان میشه توضیح بدید که گرامر روبرو زبانش منظم است یا نامنظم؟(لطفا با توضیح)
این سوال کنکور ۸۷ علوم کامپیوتره که کتاب پارسه فقط به دلیل اینکه گرامر از لحاظ ظاهری که در سوال آمده گرامر نامنظم است زبان را نامنظم فرض کرده در صورتی که به صرف نوشتن یک گرامر نامنظم برای زبانی آن زبان که نامنظم نیست درسته؟

---

با عرض پوزش خود گرامر را یادم رفت ذکر کنم
S->0S1|1S0|AA
A->0A|λ
A->A1|λ

زبانش میشه w 0n 1m 0k 1h wr که چون w و wr مستقل از متنه و اون جمله وسطی منظمه تنها درصورتی میتونیم بگیم این زبان منظمه که بتونیم به نوعی این w , wr رو بپوشانیم یا در حقیقت اون جمله وسطی بتونه w , wr رو بخوره و ناپدیدش کنه که اگه یه چنتا رشته بهش بدیم میبینیم که نمی تونه این کارو بکنه.
مثلاً به ازای w=01101

با سلام

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

این گرامر قوانینش هم خطی راسته $A \rightarrow 0A$ هم خطی چپه $A \rightarrow A1$، لذا منظم نیست.

(۲۱ آذر ۱۳۹۱ ۰۲:۴۸ ب.ظ)hp1361 نوشته شده توسط:  با سلام

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

این گرامر قوانینش هم خطی راسته $A \rightarrow 0A$ هم خطی چپه $A \rightarrow A1$، لذا منظم نیست.

موافقم

---

(۲۸ آذر ۱۳۹۱ ۱۲:۵۵ ق.ظ)fatima1537 نوشته شده توسط:  

(28 آذر ۱۳۹۱ ۱۲:۴۱ ق.ظ)jameshenas نوشته شده توسط:  s->ss برای ساخت گرامری که مثلا با a شروع شود و با a تموم بشه و با bb وسطشون باشه...به مثالم نیگاه...(البته اگه منظورتون رو درست فهمیده باشم)
s->asb
s->bsa
s->landa
حالا اگه من بخام اون چیزی رو که میخام بسازم یعنی abba رو ..آیا میتونم با گرامر بالا بسازم؟جواب مسلما نه هست
پس باید قاعده ی s->ss رو هم با گرامر اضافه کنم...

ممنون از جوابتون ولی منظور من تفاوت بین S->SS و S->AA هست

بنظرم نمیشه تو aa کنترل داشته باشیم..ولی تو ss رشته ها برابر تولید میشن یعنی منظمه تولید میشه... ولی با aa قاطی به پاتیه...(چی نوشتم ها..)
ولی مشکل داره این قواعد بقول دوستمون هم از راست و هم از چپ تولید میشه...

(۲۱ آذر ۱۳۹۱ ۱۰:۱۱ ق.ظ)lestarlight نوشته شده توسط:  S->0S1|1S0|AA
A->0A|λ
A->A1|λ

به نظر من هم منظمه.این گرامر زیان زیررو تولید میکنه:
*(*۱+*۰) هست که یک زیان منظمه . قانون اول شک برانگیزه ولی چون این گرامر اونها رو هم پوشش میده پس مشکلی بوجود نمیاد. همچنین قانون دوم و سوم رو هم میشه اصلاح و هردورو تبدیل به خطی راست یا چپ کرد طوریکه به رشته های تولید شده اشکلی وارد نکنه.

سلام. بنظر من که منظم نیست. نمیشه یه گرامر منظم برای $1^n01010^n$ نوشت. مستقل از متنه.

(۲۷ آذر ۱۳۹۱ ۱۲:۰۱ ق.ظ)Jooybari نوشته شده توسط:  سلام. بنظر من که منظم نیست. نمیشه یه گرامر منظم برای $1^n01010^n$ نوشت. مستقل از متنه.

ولی رشته هایی با همون مشخصاتی که ذکر کردید ($1^n01010^n$ ) رو میتونه تولید کنه

(۲۷ آذر ۱۳۹۱ ۱۲:۴۴ ق.ظ)fatima1537 نوشته شده توسط:  

(27 آذر ۱۳۹۱ ۱۲:۰۱ ق.ظ)Jooybari نوشته شده توسط:  سلام. بنظر من که منظم نیست. نمیشه یه گرامر منظم برای $1^n01010^n$ نوشت. مستقل از متنه.

ولی رشته هایی با همون مشخصاتی که ذکر کردید ($1^n01010^n$ ) رو میتونه تولید کنه

و همچنین نباید $1^n01010^{n 1}$ رو تولید کنه. رشته های این زبان فقط بفرم $w0^m1^n0^p1^qw^R ; w\in\{0,1\}^* , m,n,p,q\geq 0$ هستن. احتمالاً S->AA رو با S->SS اشتباه گرفتید.

(۲۷ آذر ۱۳۹۱ ۰۱:۰۲ ق.ظ)teacherpc نوشته شده توسط:  بنظر من یه نکته هست بعضی زبانها منظم گرامر منظم ندارند ولی زبانشون منظم هست اینم گرامر منظم شاید نشه براش نوشت ولی زبانش منظمه!

برای زبانهای منظم میشه گرامر منظم نوشت.

بنظر من یه نکته هست بعضی زبانها منظم گرامر منظم ندارند ولی زبانشون منظم هست اینم گرامر منظم شاید نشه براش نوشت ولی زبانش منظمه!

(۲۷ آذر ۱۳۹۱ ۰۷:۴۸ ب.ظ)Jooybari نوشته شده توسط:  و همچنین نباید $1^n01010^{n 1}$ رو تولید کنه. رشته های این زبان فقط بفرم $w0^m1^n0^p1^qw^R ; w\in \{0,1\}^* , m,n,p,q\geq 0$ هستن. احتمالاً S->AA رو با S->SS اشتباه گرفتید.

تشکر از شما . بله به نظرم اومد که شبیه هم رفتار میکنند . درسته که در S->SS نقطه شروع به صورت بازگشتی تکرار میشه ولی در S->AA و a->0a و a->1a هم این مورد هست.یه سئوال برام پیش اومده.فرق بین s->aa و s->ss چیه؟

(۲۸ آذر ۱۳۹۱ ۱۲:۲۷ ق.ظ)fatima1537 نوشته شده توسط:  فرق بین s->aa و s->ss چیه؟

S->SS گرامر رو خیلی گسترش میده و به عبارت منظم شما که همون سیکما استاره میرسه:
S->SS->SSS->SSSS->... و اگه به A بریم سیکما استار تولید میشه. ولی اگه S->AA فقط داشته باشیم:
S->AA و چون *A->a*b رو فقط داریم رشته های تولیدی محدودتره.

s->ss برای ساخت گرامری که مثلا با a شروع شود و با a تموم بشه و با bb وسطشون باشه...به مثالم نیگاه...(البته اگه منظورتون رو درست فهمیده باشم)
s->asb
s->bsa
s->landa
حالا اگه من بخام اون چیزی رو که میخام بسازم یعنی abba رو ..آیا میتونم با گرامر بالا بسازم؟جواب مسلما نه هست
پس باید قاعده ی s->ss رو هم با گرامر اضافه کنم...

(۲۸ آذر ۱۳۹۱ ۱۲:۴۱ ق.ظ)jameshenas نوشته شده توسط:  s->ss برای ساخت گرامری که مثلا با a شروع شود و با a تموم بشه و با bb وسطشون باشه...به مثالم نیگاه...(البته اگه منظورتون رو درست فهمیده باشم)
s->asb
s->bsa
s->landa
حالا اگه من بخام اون چیزی رو که میخام بسازم یعنی abba رو ..آیا میتونم با گرامر بالا بسازم؟جواب مسلما نه هست
پس باید قاعده ی s->ss رو هم با گرامر اضافه کنم...

ممنون از جوابتون ولی منظور من تفاوت بین S->SS و S->AA هست

نقل قول: منظور من تفاوت بین 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).که قوانین بعدی هم تولید کننده یک زبان منظم هستند.

فکر کنم نامنظم هست.چون S بین ۰ و ۱ هست پس تعداد بیشمار ۱ و ۰ تولید میشه که تعداد ۰ ها با تعداد ۱ ها باید برابر باشه و قانون استار هم اینجا نداریم که اونو بشکنه.
به نظر نامنظم میاد.

این زبان فقط تولید کننده رشتهایی که aوb مساوی دارند نیست.درواقع اجتماع زبانهای دارای a,b مساوی با زبانهایی که تعداد دلخواهی a,b دارند هست.و اجتماع این دو یک زبان جدید رو بوجود آورده که منظمه و رشتهایی که میپذیره جزء سیگما استار هست.پس میشه منظم

نقل قول: S->0S1|1S0|AA
A->0A|λ
A->A1|λ

---

(۰۶ دى ۱۳۹۱ ۱۰:۳۳ ق.ظ)csharpisatechnology نوشته شده توسط:  قانون استار هم اینجا نداریم که اونو بشکنه.

درواقع قانون استار همون s->aa و a->0aو a->a1 هست(چون دوتا a داریم)

قانون استار S->SS هست. اینجا ما این قانون رو نداریم. S->AA داریم. اگه A->AA هم داشتیم مشکل حل بود. ۱۰۱۰۱۰۰ رو نمیشه با این گرامر ساخت ولی ۱۰۱۰۱۰ رو میشه. من هنوز نظرم روی اینه که منظم نیست.