سلام دوستان
گرامر زبان مستقل از متن زیر چی میشه ؟
میتونین راهنمایی کنید ؟
[tex]\{0 1\}\ast-\{www\: :\: w\in\{0,1\}\ast\}[/tex]
سلام. این زبان مستقل از متن نیست. اگه تعداد wها دوتا بود اون موقع مستقل از متن میشد.
(۱۸ آبان ۱۳۹۴ ۰۲:۰۶ ق.ظ)Jooybari نوشته شده توسط: سلام. این زبان مستقل از متن نیست. اگه تعداد wها دوتا بود اون موقع مستقل از متن میشد.سلام
برای چی مستقل از متن نیست ؟
(۱۹ آبان ۱۳۹۴ ۱۲:۰۹ ق.ظ)Azar.099 نوشته شده توسط:سلام .اگر به اینصورت ww بود نیز مستقل از متن نبود(18 آبان ۱۳۹۴ ۰۲:۰۶ ق.ظ)Jooybari نوشته شده توسط: سلام. این زبان مستقل از متن نیست. اگه تعداد wها دوتا بود اون موقع مستقل از متن میشد.سلام
برای چی مستقل از متن نیست ؟
لطفا با آگاهی کافی به دوستان جواب بدهید!
(۱۹ آبان ۱۳۹۴ ۱۲:۳۹ ق.ظ)Alirezaj نوشته شده توسط:چون برای این زبان نمیتوان pda طراحی کرد(19 آبان ۱۳۹۴ ۱۲:۰۹ ق.ظ)Azar.099 نوشته شده توسط:سلام .اگر به اینصورت ww بود نیز مستقل از متن نبود(18 آبان ۱۳۹۴ ۰۲:۰۶ ق.ظ)Jooybari نوشته شده توسط: سلام. این زبان مستقل از متن نیست. اگه تعداد wها دوتا بود اون موقع مستقل از متن میشد.سلام
برای چی مستقل از متن نیست ؟
لطفا با آگاهی کافی به دوستان جواب بدهید!
(۱۹ آبان ۱۳۹۴ ۱۲:۳۹ ق.ظ)Alirezaj نوشته شده توسط:(19 آبان ۱۳۹۴ ۱۲:۰۹ ق.ظ)Azar.099 نوشته شده توسط:سلام .اگر به اینصورت ww بود نیز مستقل از متن نبود(18 آبان ۱۳۹۴ ۰۲:۰۶ ق.ظ)Jooybari نوشته شده توسط: سلام. این زبان مستقل از متن نیست. اگه تعداد wها دوتا بود اون موقع مستقل از متن میشد.سلام
برای چی مستقل از متن نیست ؟
لطفا با آگاهی کافی به دوستان جواب بدهید!
(۱۹ آبان ۱۳۹۴ ۱۲:۳۹ ق.ظ)Alirezaj نوشته شده توسط:چون برای این زبان نمیتوان pda طراحی کرد(19 آبان ۱۳۹۴ ۱۲:۰۹ ق.ظ)Azar.099 نوشته شده توسط:سلام .اگر به اینصورت ww بود نیز مستقل از متن نبود(18 آبان ۱۳۹۴ ۰۲:۰۶ ق.ظ)Jooybari نوشته شده توسط: سلام. این زبان مستقل از متن نیست. اگه تعداد wها دوتا بود اون موقع مستقل از متن میشد.سلام
برای چی مستقل از متن نیست ؟
لطفا با آگاهی کافی به دوستان جواب بدهید!
چون برای این زبان نمیتوان pda طراحی کرد
(۱۹ آبان ۱۳۹۴ ۱۲:۳۹ ق.ظ)Alirezaj نوشته شده توسط:(19 آبان ۱۳۹۴ ۱۲:۰۹ ق.ظ)Azar.099 نوشته شده توسط:سلام .اگر به اینصورت ww بود نیز مستقل از متن نبود(18 آبان ۱۳۹۴ ۰۲:۰۶ ق.ظ)Jooybari نوشته شده توسط: سلام. این زبان مستقل از متن نیست. اگه تعداد wها دوتا بود اون موقع مستقل از متن میشد.سلام
برای چی مستقل از متن نیست ؟
لطفا با آگاهی کافی به دوستان جواب بدهید!
(۱۹ آبان ۱۳۹۴ ۱۲:۳۹ ق.ظ)Alirezaj نوشته شده توسط:چون برای این زبان نمیتوان pda طراحی کرد(19 آبان ۱۳۹۴ ۱۲:۰۹ ق.ظ)Azar.099 نوشته شده توسط:سلام .اگر به اینصورت ww بود نیز مستقل از متن نبود(18 آبان ۱۳۹۴ ۰۲:۰۶ ق.ظ)Jooybari نوشته شده توسط: سلام. این زبان مستقل از متن نیست. اگه تعداد wها دوتا بود اون موقع مستقل از متن میشد.سلام
برای چی مستقل از متن نیست ؟
لطفا با آگاهی کافی به دوستان جواب بدهید!
(۱۹ آبان ۱۳۹۴ ۱۲:۳۹ ق.ظ)Alirezaj نوشته شده توسط:(19 آبان ۱۳۹۴ ۱۲:۰۹ ق.ظ)Azar.099 نوشته شده توسط:سلام .اگر به اینصورت ww بود نیز مستقل از متن نبود(18 آبان ۱۳۹۴ ۰۲:۰۶ ق.ظ)Jooybari نوشته شده توسط: سلام. این زبان مستقل از متن نیست. اگه تعداد wها دوتا بود اون موقع مستقل از متن میشد.سلام
برای چی مستقل از متن نیست ؟
لطفا با آگاهی کافی به دوستان جواب بدهید!
(۱۹ آبان ۱۳۹۴ ۱۲:۳۹ ق.ظ)Alirezaj نوشته شده توسط:چون برای این زبان نمیتوان pda طراحی کرد(19 آبان ۱۳۹۴ ۱۲:۰۹ ق.ظ)Azar.099 نوشته شده توسط:سلام .اگر به اینصورت ww بود نیز مستقل از متن نبود(18 آبان ۱۳۹۴ ۰۲:۰۶ ق.ظ)Jooybari نوشته شده توسط: سلام. این زبان مستقل از متن نیست. اگه تعداد wها دوتا بود اون موقع مستقل از متن میشد.سلام
برای چی مستقل از متن نیست ؟
چون برای این زبان نمیتوانpda طراحی کرد
لطفا با آگاهی کافی به دوستان جواب بدهید!
چون برای این زبان نمیتوان pda طراحی کرد
چرا نمیشه pda کشید ؟
دوست عزیز با استفاده از لم تزریق مستقل از متن، میشه از رشته ای مثل a^nba^nba^nb استفاده کرد تا نشون بدیم این رشته جزء زبان است و با تمام حالات شکستن رشته، میشه یه تعداد حالت برای تکرار حلقه پیدا کرد که به ازای اون تعداد، رشته جدید جزء زبان نباشه.
آقای Alirezaj زبان به فرم [tex]L=\{w_1w_2|w_1\neq w_2,|w_1|=|w_2|\}[/tex] مستقل از متنه. زبان معرفی شده در این سوال هم (اگه ۲ تا w داشته باشه) اجتماع این زبان با یک زبان منظمه (زبان شامل رشته های بطول فرد.) در نتیجه مستقل از متن میشه. اگه در مستقل از متن بودن زبان L شک دارید گرامر و استدلالش رو بگم. این زبانیه که هر سال تو انجمن روش بحث میشه.
(۱۹ آبان ۱۳۹۴ ۰۲:۴۲ ق.ظ)Jooybari نوشته شده توسط: دوست عزیز با استفاده از لم تزریق مستقل از متن، میشه از رشته ای مثل a^nba^nba^nb استفاده کرد تا نشون بدیم این رشته جزء زبان است و با تمام حالات شکستن رشته، میشه یه تعداد حالت برای تکرار حلقه پیدا کرد که به ازای اون تعداد، رشته جدید جزء زبان نباشه.لطفا به سوال دوستمون با دقت توجه کنید!
آقای Alirezaj زبان به فرم [tex]L=\{w_1w_2|w_1\neq w_2,|w_1|=|w_2|\}[/tex] مستقل از متنه. زبان معرفی شده در این سوال هم (اگه ۲ تا w داشته باشه) اجتماع این زبان با یک زبان منظمه (زبان شامل رشته های بطول فرد.) در نتیجه مستقل از متن میشه. اگه در مستقل از متن بودن زبان L شک دارید گرامر و استدلالش رو بگم. این زبانیه که هر سال تو انجمن روش بحث میشه.
*{ww:w ϵ {۰+۱}*}-{۰+۱}
زبانی که شما در پاسخ آورده اید با زبان سوال دوستمون تفاوت دارد
زبانی که شما مطرح کردهاید مستقل از متن است و هیچ شکی در آن نیست البته با همون شریط زبان مورد مثال شما
اما زبان مطرح شده در سوال با مثال شما متفاوت است!
به عنوان مثال اگر ww
بصورت ۱۱۰۱۱۰باشد این زبان دیگه مستقل از متن نیست!سوال من اینجاست که ww با w1w2 وشرایطی که شما در زبان اشاره کردید تفاوت دارد
(۱۹ آبان ۱۳۹۴ ۰۴:۱۴ ب.ظ)Alirezaj نوشته شده توسط:ببخشید چیزی که از صورت سوال پیداست تفاضل یک زبان(که این زبان مستقل از متن نیست) با یک زبان منظم است نه اجتماع!(19 آبان ۱۳۹۴ ۰۲:۴۲ ق.ظ)Jooybari نوشته شده توسط: دوست عزیز با استفاده از لم تزریق مستقل از متن، میشه از رشته ای مثل a^nba^nba^nb استفاده کرد تا نشون بدیم این رشته جزء زبان است و با تمام حالات شکستن رشته، میشه یه تعداد حالت برای تکرار حلقه پیدا کرد که به ازای اون تعداد، رشته جدید جزء زبان نباشه.لطفا به سوال دوستمون با دقت توجه کنید!
آقای Alirezaj زبان به فرم [tex]L=\{w_1w_2|w_1\neq w_2,|w_1|=|w_2|\}[/tex] مستقل از متنه. زبان معرفی شده در این سوال هم (اگه ۲ تا w داشته باشه) اجتماع این زبان با یک زبان منظمه (زبان شامل رشته های بطول فرد.) در نتیجه مستقل از متن میشه. اگه در مستقل از متن بودن زبان L شک دارید گرامر و استدلالش رو بگم. این زبانیه که هر سال تو انجمن روش بحث میشه.
*{ww:w ϵ {۰+۱}*}-{۰+۱}
زبانی که شما در پاسخ آورده اید با زبان سوال دوستمون تفاوت دارد
زبانی که شما مطرح کردهاید مستقل از متن است و هیچ شکی در آن نیست البته با همون شریط زبان مورد مثال شما
اما زبان مطرح شده در سوال با مثال شما متفاوت است!
به عنوان مثال اگر ww
بصورت ۱۱۰۱۱۰باشد این زبان دیگه مستقل از متن نیست!سوال من اینجاست که ww با w1w2 وشرایطی که شما در زبان اشاره کردید تفاوت دارد
(۱۸ آبان ۱۳۹۴ ۰۲:۰۶ ق.ظ)Jooybari نوشته شده توسط: سلام. این زبان مستقل از متن نیست. اگه تعداد wها دوتا بود اون موقع مستقل از متن میشد.
خب حالا اگر تعداد انها دو تا بود جواب چی میشه ؟
(۱۹ آبان ۱۳۹۴ ۱۱:۰۶ ب.ظ)Alirezaj نوشته شده توسط:(19 آبان ۱۳۹۴ ۰۴:۱۴ ب.ظ)Alirezaj نوشته شده توسط: لطفا به سوال دوستمون با دقت توجه کنید!ببخشید چیزی که از صورت سوال پیداست تفاضل یک زبان(که این زبان مستقل از متن نیست) با یک زبان منظم است نه اجتماع!
*{ww:w ϵ {۰+۱}*}-{۰+۱}
زبانی که شما در پاسخ آورده اید با زبان سوال دوستمون تفاوت دارد
زبانی که شما مطرح کردهاید مستقل از متن است و هیچ شکی در آن نیست البته با همون شریط زبان مورد مثال شما
اما زبان مطرح شده در سوال با مثال شما متفاوت است!
به عنوان مثال اگر ww
بصورت ۱۱۰۱۱۰باشد این زبان دیگه مستقل از متن نیست!سوال من اینجاست که ww با w1w2 وشرایطی که شما در زبان اشاره کردید تفاوت دارد
زبان [tex]L_1=\{0 1\}^*-\{ww|w\in\{0 1\}^*\}[/tex] یعنی زبان سیکمااستار منهای زبانی که از دو رشته مشابه تشکیل شده اند. یه تعریف دیگه از این زبان این میشه: زبانی که نشه رشته های اون رو به شکل دو رشته مشابه پشت سر هم نوشت. این زبان با زبان [tex]L_2=((0 1)(0 1))^*(0 1)\cup\{w_1w_2|w_1\neq w_2,|w_1|=|w_2|\}[/tex] برابره.
(۲۰ آبان ۱۳۹۴ ۰۲:۴۵ ق.ظ)Jooybari نوشته شده توسط:(19 آبان ۱۳۹۴ ۱۱:۰۶ ب.ظ)Alirezaj نوشته شده توسط:(19 آبان ۱۳۹۴ ۰۴:۱۴ ب.ظ)Alirezaj نوشته شده توسط: لطفا به سوال دوستمون با دقت توجه کنید!ببخشید چیزی که از صورت سوال پیداست تفاضل یک زبان(که این زبان مستقل از متن نیست) با یک زبان منظم است نه اجتماع!
*{ww:w ϵ {۰+۱}*}-{۰+۱}
زبانی که شما در پاسخ آورده اید با زبان سوال دوستمون تفاوت دارد
زبانی که شما مطرح کردهاید مستقل از متن است و هیچ شکی در آن نیست البته با همون شریط زبان مورد مثال شما
اما زبان مطرح شده در سوال با مثال شما متفاوت است!
به عنوان مثال اگر ww
بصورت ۱۱۰۱۱۰باشد این زبان دیگه مستقل از متن نیست!سوال من اینجاست که ww با w1w2 وشرایطی که شما در زبان اشاره کردید تفاوت دارد
زبان [tex]L_1=\{0 1\}^*-\{ww|w\in\{0 1\}^*\}[/tex] یعنی زبان سیکمااستار منهای زبانی که از دو رشته مشابه تشکیل شده اند. یه تعریف دیگه از این زبان این میشه: زبانی که نشه رشته های اون رو به شکل دو رشته مشابه پشت سر هم نوشت. این زبان با زبان [tex]L_2=((0 1)(0 1))^*(0 1)\cup\{w_1w_2|w_1\neq w_2,|w_1|=|w_2|\}[/tex] برابره.
خب میشه گرامر همین را بگین .. یعنی دو تا ww
(۲۰ آبان ۱۳۹۴ ۰۳:۰۶ ق.ظ)Azar.099 نوشته شده توسط:(20 آبان ۱۳۹۴ ۰۲:۴۵ ق.ظ)Jooybari نوشته شده توسط:(19 آبان ۱۳۹۴ ۱۱:۰۶ ب.ظ)Alirezaj نوشته شده توسط:(19 آبان ۱۳۹۴ ۰۴:۱۴ ب.ظ)Alirezaj نوشته شده توسط: لطفا به سوال دوستمون با دقت توجه کنید!ببخشید چیزی که از صورت سوال پیداست تفاضل یک زبان(که این زبان مستقل از متن نیست) با یک زبان منظم است نه اجتماع!
*{ww:w ϵ {۰+۱}*}-{۰+۱}
زبانی که شما در پاسخ آورده اید با زبان سوال دوستمون تفاوت دارد
زبانی که شما مطرح کردهاید مستقل از متن است و هیچ شکی در آن نیست البته با همون شریط زبان مورد مثال شما
اما زبان مطرح شده در سوال با مثال شما متفاوت است!
به عنوان مثال اگر ww
بصورت ۱۱۰۱۱۰باشد این زبان دیگه مستقل از متن نیست!سوال من اینجاست که ww با w1w2 وشرایطی که شما در زبان اشاره کردید تفاوت دارد
زبان [tex]L_1=\{0 1\}^*-\{ww|w\in\{0 1\}^*\}[/tex] یعنی زبان سیکمااستار منهای زبانی که از دو رشته مشابه تشکیل شده اند. یه تعریف دیگه از این زبان این میشه: زبانی که نشه رشته های اون رو به شکل دو رشته مشابه پشت سر هم نوشت. این زبان با زبان [tex]L_2=((0 1)(0 1))^*(0 1)\cup\{w_1w_2|w_1\neq w_2,|w_1|=|w_2|\}[/tex] برابره.
خب میشه گرامر همین را بگین .. یعنی دو تا ww
این موضوع آخری که شما مطرح کرده اید کاملا درسته.من فکر کردم منظور شما اینه که این زبان به تنهای مستقل از متن که همینطور که قبلا اشاره کردم اینطور نیست.اگر مثالی روکه من در پاسخ شما آورده بودم رو دوباره بخوانید متوجه خواهید شد که منظور من این زبان به تنهای بوده {*{ww|wϵ {۰+۱}}و مثال من که گفتم این زبان مستقل از متن نیست ۱۱۰۱۱۰= ww.
(۲۰ آبان ۱۳۹۴ ۱۱:۵۵ ق.ظ)Alirezaj نوشته شده توسط: این موضوع آخری که شما مطرح کرده اید کاملا درسته.من فکر کردم منظور شما اینه که این زبان به تنهای مستقل از متن که همینطور که قبلا اشاره کردم اینطور نیست.اگر مثالی روکه من در پاسخ شما آورده بودم رو دوباره بخوانید متوجه خواهید شد که منظور من این زبان به تنهای بوده {*{ww|wϵ {۰+۱}}و مثال من که گفتم این زبان مستقل از متن نیست ۱۱۰۱۱۰= ww.
بله. این زبان مستقل از متن نیست.
(۲۰ آبان ۱۳۹۴ ۱۱:۵۵ ق.ظ)Alirezaj نوشته شده توسط: خب میشه گرامر همین را بگین .. یعنی دو تا ww
گرامر زبان [tex]L_1=\{0 1\}^*-\{ww|w\in\{0 1\}^*\}[/tex] میشه:
[tex]S\to AB|BA|C[/tex]
[tex]A\to PAP|a[/tex]
[tex]B\to BPB|b[/tex]
[tex]C\to PPC|P[/tex]
[tex]P\to a|b[/tex]
این گرامر از روی زبان L2 قابل فهم تره. قسمت منظم زبان اون عبارتیه که با C شروع میشه.
(۲۰ آبان ۱۳۹۴ ۰۲:۱۵ ب.ظ)Jooybari نوشته شده توسط:(20 آبان ۱۳۹۴ ۱۱:۵۵ ق.ظ)Alirezaj نوشته شده توسط: این موضوع آخری که شما مطرح کرده اید کاملا درسته.من فکر کردم منظور شما اینه که این زبان به تنهای مستقل از متن که همینطور که قبلا اشاره کردم اینطور نیست.اگر مثالی روکه من در پاسخ شما آورده بودم رو دوباره بخوانید متوجه خواهید شد که منظور من این زبان به تنهای بوده {*{ww|wϵ {۰+۱}}و مثال من که گفتم این زبان مستقل از متن نیست ۱۱۰۱۱۰= ww.
بله. این زبان مستقل از متن نیست.
(۲۰ آبان ۱۳۹۴ ۱۱:۵۵ ق.ظ)Alirezaj نوشته شده توسط: خب میشه گرامر همین را بگین .. یعنی دو تا ww
گرامر زبان [tex]L_1=\{0 1\}^*-\{ww|w\in\{0 1\}^*\}[/tex] میشه:
[tex]S\to AB|BA|C[/tex]
[tex]A\to PAP|a[/tex]
[tex]B\to BPB|b[/tex]
[tex]C\to PPC|P[/tex]
[tex]P\to a|b[/tex]
این گرامر از روی زبان L2 قابل فهم تره. قسمت منظم زبان اون عبارتیه که با C شروع میشه.
خیلی متشکرم از پاسخگوییتون
ولی یه چیزی . من هنوز متوجه نشدم که چرا سه تا www نمیشه ؟ و در این حالت مستقل از متن نیست ؟
خب مگه نباید از تمام حالت یعنی از سیگما استار تمام حالاتی که سه تا رشته پشت هم مثل هم میشن را کم کنه ؟
نقل قول: زبان معرفی شده در این سوال هم (اگه ۲ تا w داشته باشه) اجتماع این زبان با یک زبان منظمه (زبان شامل رشته های بطول فرد.)این جملتون را هم متوجه نمیشم ...
(۲۰ آبان ۱۳۹۴ ۰۵:۵۲ ب.ظ)Azar.099 نوشته شده توسط: ولی یه چیزی . من هنوز متوجه نشدم که چرا سه تا www نمیشه ؟ و در این حالت مستقل از متن نیست ؟
خب مگه نباید از تمام حالت یعنی از سیگما استار تمام حالاتی که سه تا رشته پشت هم مثل هم میشن را کم کنه ؟
نقل قول: زبان معرفی شده در این سوال هم (اگه ۲ تا w داشته باشه) اجتماع این زبان با یک زبان منظمه (زبان شامل رشته های بطول فرد.)این جملتون را هم متوجه نمیشم ...
اثبات مستقل از متن نبودن این زبان ساده نیست. برای استفاده از لم ترزیق باید یه رشته ای رو مثال بزنیم که به فرم www نباشه و بتونیم در تمام حالات شکستنش، اونو به فرم www در بیاریم. من نتونستم همچین رشته ای رو پیدا کنم. (نتونستم اثبات کنم که مستقل از متن نیست. به نظرم باید از قواعد اجتماع و اشتراک زبانها کمک بگیریم.) ولی شباهتی به زبانهای مستقل از متن نداره. تفاوتی که این حالت با ww داره اینه که در سه تا رشته پشت سر هم ما نمیتونیم iامین حرف از رشته دوم رو با بقیه مقایسه کنیم.
در حالتی که دو تا رشته مشابه پشت سر هم داریم میتونیم با یه روش خاص، iامین حرفشون رو بررسی کنیم. با تکرار غیر قطعی این کار هم میتونیم به جواب برسیم.
برای حالتی که نباید ww داشته باشیم، در صورتی که طول رشته فرد باشه، رشته مورد قبوله. برای رشته های به طول زوج باید از یه زبان مستقل از متن غیر قطعی استفاده کنیم. اجتماع گرفتنشون هم سادست.