(۱۷ اردیبهشت ۱۳۹۵ ۰۳:۰۰ ب.ظ)freidoony نوشته شده توسط:  

(17 اردیبهشت ۱۳۹۵ ۰۲:۵۶ ب.ظ)IranianWizard نوشته شده توسط:  زبان اول مجموع دو زبان مستقل قطعی بود که میشه غیر قطعی زبان دوم هم منظم بود که اشتراکشون می شد مستقل غیر قطعی (گزینه ۱)

L2 با یک ختم می شد در صورتی که ماشین جملاتی داشت که با صفر هم ختم می شد
زبان مستقل از متن قطعی هم تحت اجتماع بسته نیست

(۱۷ اردیبهشت ۱۳۹۵ ۰۳:۰۷ ب.ظ)IranianWizard نوشته شده توسط:  

(17 اردیبهشت ۱۳۹۵ ۰۳:۰۰ ب.ظ)freidoony نوشته شده توسط:  

(17 اردیبهشت ۱۳۹۵ ۰۲:۵۶ ب.ظ)IranianWizard نوشته شده توسط:  زبان اول مجموع دو زبان مستقل قطعی بود که میشه غیر قطعی زبان دوم هم منظم بود که اشتراکشون می شد مستقل غیر قطعی (گزینه ۱)

L2 با یک ختم می شد در صورتی که ماشین جملاتی داشت که با صفر هم ختم می شد
زبان مستقل از متن قطعی هم تحت اجتماع بسته نیست

در مورد L2 دقیقا یادم نیست.ولی من فک میکنم برابر بودند.
ولی در مورد مستقل قطعی:
دوست عزیز درسته اجتماع دو زبان مستقل قطعی لزوما مستقل قطعی نیست!
این یعنی اینکه نمیشه بطور قطع بگیم که اجتماع دو زبان مستقل قطعی، بازم مستقل قطعی هستش! ولی ممکنه اجتماع برخی از زبانهای قطعی ،بازم قطعی بشه!اجتماع این دو زبان قطعی هم، به وضوح قطعیه.میتونید به راحتی واسش DPDA بکشید!

(۱۷ اردیبهشت ۱۳۹۵ ۰۲:۵۳ ب.ظ)ememem نوشته شده توسط:  

(17 اردیبهشت ۱۳۹۵ ۰۲:۴۱ ب.ظ)IranianWizard نوشته شده توسط:  

(17 اردیبهشت ۱۳۹۵ ۰۱:۵۳ ب.ظ)mohamad moo نوشته شده توسط:  

(17 اردیبهشت ۱۳۹۵ ۰۱:۵۲ ب.ظ)saeid1389 نوشته شده توسط:  سوال یک کامپایلر

به علت برخورد first/follow ، گرامر (۱)LL نیست

پس تناقض داشت

شما LL(1) بودن رو دارید اشتباه تحلیل میکنید!
گرامری LL(1) هستش که تمام قواعد آن،برخورد first/first و برخورد first/follow نداشته باشه!
ّ
در این سوال گفته شده یکی از متغیر های گرامر A هستش که دارای قاعده تولید های [tex]A\: \rightarrow\: \alpha\: \mid\: \: \beta[/tex] هستش.(پس متغیرها و قواعد دیگه ای هم داره)...
از طرفی طبق فرض سوال :قاعده [tex]\alpha[/tex] میتونه لامبدا رو تولید کنه ولی [tex]\beta[/tex] لامبدا رو تولید نمیکنه!
و شرط اول سوال: [tex]first(\alpha)\: \cap\: \: first(\beta)\: =\: \varnothing[/tex] هستش ،پس یعنی این متغیر برخورد first/first نداره.
و شرط دوم سوال: [tex]follow(A)\: \cap\: \: first(\beta)\: =\: \varnothing[/tex] هستش، پس یعنی این متغیر برخورد First/Follow نداره!
همونطور که میدونید برخورد first/follow یعنی follow متغیر مورد نظر،اشتراکش با قاعده ای که لامبدا رو تولید نمیکنه،تهی باشه!!! که اینجا هم همینطوره!
و شرط سوم میگه که : [tex]follow(A)\: \cap\: \: first(A)\: \ne\: \varnothing[/tex] که هیچ مشکلی نداره و میتونه اتفاق بیفته!!بطور مثال گرامر زیر رو در نظر بگیرید:که هر سه شرط صورت سوال رو داره!

[tex]A\: \rightarrow\: BC\: \mid\: \: g[/tex]
[tex]B\: \rightarrow\: b\: \mid\: \: \lambda[/tex]
[tex]C\: \rightarrow\: dD\: \mid\: \: \lambda[/tex]
[tex]D\: \rightarrow\: Ab\: \mid\: \: \lambda[/tex]

در متغیر A:
[tex]First(\alpha)\: =\: First\: (BC)\: =\{b\: ,\: d\: ,\: \lambda\}[/tex]
[tex]First(\beta)\: =\: First\: (g)\: =\{g\}[/tex]
پس برخورد first/first نداره.

[tex]Follow(A)\: =\: \{\: \$\: ,\: \: b\}[/tex]
و چون [tex]Follow(A)\: \cap\: First(\beta)\: =\: \{\: \$\: ,\: b\}\: \cap\: \: \{g\}\: =\: \varnothing[/tex]
پس برخورد first/follow هم نداره در حالیکه [tex]Follow(A)\: \cap\: First(A)\: =\: \{\: \$\: ,\: b\}\: \cap\: \: \{b,c,\: \lambda\: ,\: g\}\: =\{b\}\: \ne\varnothing[/tex] هستش!

پس با این مثال مشخص شد که هر سه شرط سوال درست هستش و هیچ تناقضی نیست.وچون زوج قاعده A ، شرط LL(1) بودن رو نقض نمیکنه ،LL(1) بودن یا نبودن گرامر بستگی به قواعد دیگر گرامر داره.(که در متن سوال اشاره شده زوج قاعده A بخشی از قواعد یک گرامر است)

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

(۱۷ اردیبهشت ۱۳۹۵ ۰۳:۱۶ ب.ظ)IranianWizard نوشته شده توسط:  

(17 اردیبهشت ۱۳۹۵ ۰۲:۵۳ ب.ظ)ememem نوشته شده توسط:  

(17 اردیبهشت ۱۳۹۵ ۰۲:۴۱ ب.ظ)IranianWizard نوشته شده توسط:  

(17 اردیبهشت ۱۳۹۵ ۰۱:۵۳ ب.ظ)mohamad moo نوشته شده توسط:  

(17 اردیبهشت ۱۳۹۵ ۰۱:۵۲ ب.ظ)saeid1389 نوشته شده توسط:  سوال یک کامپایلر

به علت برخورد first/follow ، گرامر (۱)LL نیست

پس تناقض داشت

شما LL(1) بودن رو دارید اشتباه تحلیل میکنید!
گرامری LL(1) هستش که تمام قواعد آن،برخورد first/first و برخورد first/follow نداشته باشه!
ّ
در این سوال گفته شده یکی از متغیر های گرامر A هستش که دارای قاعده تولید های [tex]A\: \rightarrow\: \alpha\: \mid\: \: \beta[/tex] هستش.(پس متغیرها و قواعد دیگه ای هم داره)...
از طرفی طبق فرض سوال :قاعده [tex]\alpha[/tex] میتونه لامبدا رو تولید کنه ولی [tex]\beta[/tex] لامبدا رو تولید نمیکنه!
و شرط اول سوال: [tex]first(\alpha)\: \cap\: \: first(\beta)\: =\: \varnothing[/tex] هستش ،پس یعنی این متغیر برخورد first/first نداره.
و شرط دوم سوال: [tex]follow(A)\: \cap\: \: first(\beta)\: =\: \varnothing[/tex] هستش، پس یعنی این متغیر برخورد First/Follow نداره!
همونطور که میدونید برخورد first/follow یعنی follow متغیر مورد نظر،اشتراکش با قاعده ای که لامبدا رو تولید نمیکنه،تهی باشه!!! که اینجا هم همینطوره!
و شرط سوم میگه که : [tex]follow(A)\: \cap\: \: first(A)\: \ne\: \varnothing[/tex] که هیچ مشکلی نداره و میتونه اتفاق بیفته!!بطور مثال گرامر زیر رو در نظر بگیرید:که هر سه شرط صورت سوال رو داره!

[tex]A\: \rightarrow\: BC\: \mid\: \: g[/tex]
[tex]B\: \rightarrow\: b\: \mid\: \: \lambda[/tex]
[tex]C\: \rightarrow\: dD\: \mid\: \: \lambda[/tex]
[tex]D\: \rightarrow\: Ab\: \mid\: \: \lambda[/tex]

در متغیر A:
[tex]First(\alpha)\: =\: First\: (BC)\: =\{b\: ,\: d\: ,\: \lambda\}[/tex]
[tex]First(\beta)\: =\: First\: (g)\: =\{g\}[/tex]
پس برخورد first/first نداره.

[tex]Follow(A)\: =\: \{\: \$\: ,\: \: b\}[/tex]
و چون [tex]Follow(A)\: \cap\: First(\beta)\: =\: \{\: \$\: ,\: b\}\: \cap\: \: \{g\}\: =\: \varnothing[/tex]
پس برخورد first/follow هم نداره در حالیکه [tex]Follow(A)\: \cap\: First(A)\: =\: \{\: \$\: ,\: b\}\: \cap\: \: \{b,c,\: \lambda\: ,\: g\}\: =\{b\}\: \ne\varnothing[/tex] هستش!

پس با این مثال مشخص شد که هر سه شرط سوال درست هستش و هیچ تناقضی نیست.وچون زوج قاعده A ، شرط LL(1) بودن رو نقض نمیکنه ،LL(1) بودن یا نبودن گرامر بستگی به قواعد دیگر گرامر داره.(که در متن سوال اشاره شده زوج قاعده A بخشی از قواعد یک گرامر است)

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

سوال گفته بود که متغیر A این قواعد رو داره(دیگه غیر از این قواعد،A دیگه قواعدی نداره)
ولی اینم گفته بود که زوج قاعده A ، بخشی از قواعد یک گرامر هستش.پس یعنی این گرامر قواعد دیگه ای هم داره.
و اگه زوج قاعده A ، شرط LL(1) بودن رو نقض کنه،که میتونیم بگیم این گرامر LL(1) نیست.
ولی اگه شرط LL(1) بودن رو نقض نکنه،نمیتونیم بگیم که LL(1) هست یا نه!چون باید قواعد دیگر گرامر بررسی بشه. و بستگی به اون قواعد داره.

(۱۷ اردیبهشت ۱۳۹۵ ۰۱:۴۲ ب.ظ)freidoony نوشته شده توسط:  چهاررمی همه موارد می شد ( Lambeda)

ششمی که خدا بده برکت حل کردنش یک ساعت طول می کشید

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

(۱۷ اردیبهشت ۱۳۹۵ ۰۱:۵۰ ب.ظ)saeid1389 نوشته شده توسط:  

(17 اردیبهشت ۱۳۹۵ ۰۱:۴۹ ب.ظ)mohamad moo نوشته شده توسط:  دایجسترا ۴ میشد!

من ۶ زدم

(۱۷ اردیبهشت ۱۳۹۵ ۰۳:۱۹ ب.ظ)IranianWizard نوشته شده توسط:  

(17 اردیبهشت ۱۳۹۵ ۰۱:۴۲ ب.ظ)freidoony نوشته شده توسط:  چهاررمی همه موارد می شد ( Lambeda)

ششمی که خدا بده برکت حل کردنش یک ساعت طول می کشید

خیر همه موارد نمیشد!این سوال از فصل اول کتاب میشل طرح شده بود.
اگر که اشاره گر بخش اول و بخش دوم لیست،هر کدام به طور جدا به یک لیست AB اشاره میکردن،اونوقت دوتا از گزینه ها درست میشد.
ولی اینجا دقت کنید بخش اول و دوم لیست،هر دو به یک لیست AB اشاره میکردن! و جواب گزینه ای میشه که تنها یک cons 'A 'B داشته باشه.
فک کنم این بود:
[tex](lamba\: (x,x)\: (cons\: x\: x))\ :(cons\: 'A\: 'B)[/tex]

ششمین سوال هم ،میشد گزینه ای که طولانی تر بود.اولش aba بود فک کنم.اینم از فصل اول کتاب میشل طرح شده!کلا فصل اول کتاب میشل در مورد حساب لامبدا و زبان Lisp و ارتباط آنها باهم هستش.که امروز دو سوال ازش طرح شده بود.

(۱۷ اردیبهشت ۱۳۹۵ ۰۳:۴۲ ب.ظ)farahdsa نوشته شده توسط:  

(17 اردیبهشت ۱۳۹۵ ۰۳:۱۹ ب.ظ)IranianWizard نوشته شده توسط:  

(17 اردیبهشت ۱۳۹۵ ۰۱:۴۲ ب.ظ)freidoony نوشته شده توسط:  چهاررمی همه موارد می شد ( Lambeda)

ششمی که خدا بده برکت حل کردنش یک ساعت طول می کشید

خیر همه موارد نمیشد!این سوال از فصل اول کتاب میشل طرح شده بود.
اگر که اشاره گر بخش اول و بخش دوم لیست،هر کدام به طور جدا به یک لیست AB اشاره میکردن،اونوقت دوتا از گزینه ها درست میشد.
ولی اینجا دقت کنید بخش اول و دوم لیست،هر دو به یک لیست AB اشاره میکردن! و جواب گزینه ای میشه که تنها یک cons 'A 'B داشته باشه.
فک کنم این بود:
[tex](lamba\: (x,x)\: (cons\: x\: x))\ :(cons\: 'A\: 'B)[/tex]

ششمین سوال هم ،میشد گزینه ای که طولانی تر بود.اولش aba بود فک کنم.اینم از فصل اول کتاب میشل طرح شده!کلا فصل اول کتاب میشل در مورد حساب لامبدا و زبان Lisp و ارتباط آنها باهم هستش.که امروز دو سوال ازش طرح شده بود.

شما این منبع رو از کجا پیدا کردین ؟:دی

(۱۷ اردیبهشت ۱۳۹۵ ۰۲:۴۱ ب.ظ)IranianWizard نوشته شده توسط:  [quote='mohamad moo' pid='402482' dateline='1462526620']
[quote='saeid1389' pid='402481' dateline='1462526529']
سوال یک کامپایلر

به علت برخورد first/follow ، گرامر (۱)LL نیس

[tex]A\: \rightarrow\: BC\: \mid\: \: g[/tex]
[tex]B\: \rightarrow\: b\: \mid\: \: \lambda[/tex]
[tex]C\: \rightarrow\: dD\: \mid\: \: \lambda[/tex]
[tex]D\: \rightarrow\: Ab\: \mid\: \: \lambda[/tex]

پس با این مثال مشخص شد که هر سه شرط سوال درست هستش و هیچ تناقضی نیست.وچون زوج قاعده A ، شرط LL(1) بودن رو نقض نمیکنه ،LL(1) بودن یا نبودن گرامر بستگی به قواعد دیگر گرامر داره.(که در متن سوال اشاره شده زوج قاعده A بخشی از قواعد یک گرامر است)

(۱۷ اردیبهشت ۱۳۹۵ ۰۴:۰۴ ب.ظ)kebrit نوشته شده توسط:  

(17 اردیبهشت ۱۳۹۵ ۰۲:۴۱ ب.ظ)IranianWizard نوشته شده توسط:  [quote='mohamad moo' pid='402482' dateline='1462526620']
[quote='saeid1389' pid='402481' dateline='1462526529']
سوال یک کامپایلر

به علت برخورد first/follow ، گرامر (۱)LL نیس

[tex]A\: \rightarrow\: BC\: \mid\: \: g[/tex]
[tex]B\: \rightarrow\: b\: \mid\: \: \lambda[/tex]
[tex]C\: \rightarrow\: dD\: \mid\: \: \lambda[/tex]
[tex]D\: \rightarrow\: Ab\: \mid\: \: \lambda[/tex]

پس با این مثال مشخص شد که هر سه شرط سوال درست هستش و هیچ تناقضی نیست.وچون زوج قاعده A ، شرط LL(1) بودن رو نقض نمیکنه ،LL(1) بودن یا نبودن گرامر بستگی به قواعد دیگر گرامر داره.(که در متن سوال اشاره شده زوج قاعده A بخشی از قواعد یک گرامر است)

تو اینجا مگه Follow(A)∩First(BC) = b
که BC همون آلفا هست ، تناقض نیست ؟

(۱۷ اردیبهشت ۱۳۹۵ ۰۴:۱۰ ب.ظ)IranianWizard نوشته شده توسط:  خیر.برخورد first/follow میگه که follow متغیر داده شده،اشتراکش با قاعده ای که لامبدا تولید نمیکنه،تهی باشه.
مبتونید جدول LL(1) شو بکشید(فقط سطر A کافیه)

(۱۷ اردیبهشت ۱۳۹۵ ۰۴:۲۶ ب.ظ)kebrit نوشته شده توسط:  

(17 اردیبهشت ۱۳۹۵ ۰۴:۱۰ ب.ظ)IranianWizard نوشته شده توسط:  خیر.برخورد first/follow میگه که follow متغیر داده شده،اشتراکش با قاعده ای که لامبدا تولید نمیکنه،تهی باشه.
مبتونید جدول LL(1) شو بکشید(فقط سطر A کافیه)

تا جایی که من میدونم اشتراکش با قاعده ای که لمبدا تولید میکنه باید تهی باشه
متاسفانه گوشی ندارم عکس بگیرم اما میتونید توی کتاب یا web پیدا کنید (مثلا :
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
)
من کتاب پوران ۹۴ رو دارم ص ۱۱۶