۰
subtitle
ارسال: #۱
قطعی بودن زبان L={a^p b^q a^p b^s : p,q,s>=0}
سلام. آیا زبان زیر مستقل از متن قطعی هستش یا غیر قطعی؟
[tex]L\: =\: \{a^p\: b^q\: a^p\: b^s\: \: :\: \: p,q,s\: \ge0\}[/tex]
تو لینک زیر هم در موردش بحث شده و گفته شده که مستقل از متن غیر قطعی هستش .
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
ولی من راستش شک دارم نسبت به غیر قطعی بودنش.بنظرم قطعی هستش.
من از خاصیت بستاری زبانهای مستقل از متن استفاده کردم و زبان معادل زیر رو بدست آوردم:
[tex]L\: =\: \{a^p\: b^q\: a^p\: b^s\: \: :\: \: p,q\ge1\: ,\: s\ge0\}\: \cup\: \{b^{\ast}\}\: \cup\: \{\: a^{2p}\: b^s\: :\: p\ge1\: \: ,\: \: s\ge0\}[/tex]
که چون مجموعه اولی مستقل از متن قطعی و مجموعه دوم و سوم منظم هستند.پس اجتماعشون مستقل از متن قطعی میشه.و در نتیجه این زبان یک زبان مستقل از متن قطعی هستش.
آیا این استدلالم درسته؟
[tex]L\: =\: \{a^p\: b^q\: a^p\: b^s\: \: :\: \: p,q,s\: \ge0\}[/tex]
تو لینک زیر هم در موردش بحث شده و گفته شده که مستقل از متن غیر قطعی هستش .
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
ولی من راستش شک دارم نسبت به غیر قطعی بودنش.بنظرم قطعی هستش.
من از خاصیت بستاری زبانهای مستقل از متن استفاده کردم و زبان معادل زیر رو بدست آوردم:
[tex]L\: =\: \{a^p\: b^q\: a^p\: b^s\: \: :\: \: p,q\ge1\: ,\: s\ge0\}\: \cup\: \{b^{\ast}\}\: \cup\: \{\: a^{2p}\: b^s\: :\: p\ge1\: \: ,\: \: s\ge0\}[/tex]
که چون مجموعه اولی مستقل از متن قطعی و مجموعه دوم و سوم منظم هستند.پس اجتماعشون مستقل از متن قطعی میشه.و در نتیجه این زبان یک زبان مستقل از متن قطعی هستش.
آیا این استدلالم درسته؟
۰
ارسال: #۲
RE: قطعی بودن زبان L={a^p b^q a^p b^s : p,q,s>=0}
سلام
از کجا می گید که اجتماع منظم و مستقل از متن قطعی یک زبان مستقل از متن قطعی است؟
من چنین چیزی یادم نمیاد
ولی تونستم براش یه اتوماتون قطعی بنویسم:
اوول که a ها را می بینم دو پشته پوش کنیم اما در هنگام پوش کردن اینو هم محاسبه کنیم که a هامون تا اینجای کار زوج بودن یا فرد
اگر زوج بودن که بعدش اگه b بیاد می پذیریم و اگه بعد از b ها باز هم a بیاد با a های داخل پشته مقایسه می کنیم
امام اگر تعداد a های اولیه فرد باشند حتما باید بعدش b بیاد و بعد از b ها باید یه سری a بیاد که با a های داخل پشته مقایسه بشن
اینم جزییات کامل اتوماتون من
که حالت های q0,q2,q3,q5 پایانی هستند
پوش کردن a ها و تشخیص زوج و فرد بودن آن ها
[tex]\delta(q_0,a,z)=(q_1,az)[/tex]
[tex]\delta(q_0,a,a)=(q_1,aa)[/tex]
[tex]\delta(q_1,a,a)=(q_0,aa)[/tex]
تعداد زوج a ها: (نماد "؟" یعنی هر چی در پشته بود همون رو می ذاریم باشه بهش دست نمی زنیم)
[tex]\delta(q_0,b,?)=(q_2,?)[/tex]
[tex]\delta(q_2,b,?)=(q_2,?)[/tex]
[tex]\delta(q_2,a,a)=(q_3,\lambda)[/tex]
[tex]\delta(q_3,a,a)=(q_3,\lambda)[/tex]
[tex]\delta(q_3,b,?)=(q_5,?)[/tex]
[tex]\delta(q_5,b,?)=(q_5,?)[/tex]
تعداد a های فرد:
[tex]\delta(q_1,b,?)=(q_4,?)[/tex]
[tex]\delta(q_4,b,?)=(q_4,?)[/tex]
[tex]\delta(q_4,a,a)=(q_3,\lambda)[/tex]
از کجا می گید که اجتماع منظم و مستقل از متن قطعی یک زبان مستقل از متن قطعی است؟
من چنین چیزی یادم نمیاد
ولی تونستم براش یه اتوماتون قطعی بنویسم:
اوول که a ها را می بینم دو پشته پوش کنیم اما در هنگام پوش کردن اینو هم محاسبه کنیم که a هامون تا اینجای کار زوج بودن یا فرد
اگر زوج بودن که بعدش اگه b بیاد می پذیریم و اگه بعد از b ها باز هم a بیاد با a های داخل پشته مقایسه می کنیم
امام اگر تعداد a های اولیه فرد باشند حتما باید بعدش b بیاد و بعد از b ها باید یه سری a بیاد که با a های داخل پشته مقایسه بشن
اینم جزییات کامل اتوماتون من
که حالت های q0,q2,q3,q5 پایانی هستند
پوش کردن a ها و تشخیص زوج و فرد بودن آن ها
[tex]\delta(q_0,a,z)=(q_1,az)[/tex]
[tex]\delta(q_0,a,a)=(q_1,aa)[/tex]
[tex]\delta(q_1,a,a)=(q_0,aa)[/tex]
تعداد زوج a ها: (نماد "؟" یعنی هر چی در پشته بود همون رو می ذاریم باشه بهش دست نمی زنیم)
[tex]\delta(q_0,b,?)=(q_2,?)[/tex]
[tex]\delta(q_2,b,?)=(q_2,?)[/tex]
[tex]\delta(q_2,a,a)=(q_3,\lambda)[/tex]
[tex]\delta(q_3,a,a)=(q_3,\lambda)[/tex]
[tex]\delta(q_3,b,?)=(q_5,?)[/tex]
[tex]\delta(q_5,b,?)=(q_5,?)[/tex]
تعداد a های فرد:
[tex]\delta(q_1,b,?)=(q_4,?)[/tex]
[tex]\delta(q_4,b,?)=(q_4,?)[/tex]
[tex]\delta(q_4,a,a)=(q_3,\lambda)[/tex]
۰
ارسال: #۳
RE: قطعی بودن زبان L={a^p b^q a^p b^s : p,q,s>=0}
سلام. وقت بخیر.
به نظرم با تجذیه کردن به شکلی که زبان حاصل از اجتماع یا اشتراک یک زبان مستقل از متن قطعی با چند زبان منظم تشکیل بشه، زبان مستقل از متن قطعی خواهد بود. دلیل استدلالم اینه که دلیل غیرقطعی شدن ترکیب زبان های مستقل از متن اینه که همشون میخان از پشته استفاده کنن. ولی اگه فقط یکی از زبان ها با پشته کار داشته باشه میشه به روشی مشابه ترکیب زبانهای منظم، ماشین زبان ترکیبی رو ساخت و ساختار پشته رو با توجه به زبان مستقل از متن درنظر گرفت. البته این استدلال و نظر خودمه و خانم fatemeh69 توی این مباحث اطلاعات و مطالعات بیشتری دارن.
به نظرم با تجذیه کردن به شکلی که زبان حاصل از اجتماع یا اشتراک یک زبان مستقل از متن قطعی با چند زبان منظم تشکیل بشه، زبان مستقل از متن قطعی خواهد بود. دلیل استدلالم اینه که دلیل غیرقطعی شدن ترکیب زبان های مستقل از متن اینه که همشون میخان از پشته استفاده کنن. ولی اگه فقط یکی از زبان ها با پشته کار داشته باشه میشه به روشی مشابه ترکیب زبانهای منظم، ماشین زبان ترکیبی رو ساخت و ساختار پشته رو با توجه به زبان مستقل از متن درنظر گرفت. البته این استدلال و نظر خودمه و خانم fatemeh69 توی این مباحث اطلاعات و مطالعات بیشتری دارن.
۰
ارسال: #۴
RE: قطعی بودن زبان L={a^p b^q a^p b^s : p,q,s>=0}
(۱۰ اردیبهشت ۱۳۹۵ ۰۵:۴۱ ق.ظ)fatemeh69 نوشته شده توسط: سلامواقعا ممنونم.خیلی زحمت کشیدید.کاملا متوجه شدم.
از کجا می گید که اجتماع منظم و مستقل از متن قطعی یک زبان مستقل از متن قطعی است؟
من چنین چیزی یادم نمیاد
من خودم نتونستم DPDA این زبانو بکشم.به همین دلیل از روش خاصیت های بستاری زبانها استفاده کردم.
دلیل اینکه گفتم اجتماع یک زبان مستقل از متن قطعی و یک زبان منظم، مستقل از متن قطعی خواهد شد اینه که:
همانطور که میدونید زبانهای مستقل از متن قطعی تحت اشتراک منظم بسته هستند و تو اینترنت هم در موردش هست و اثبات شده ست.
پس اگر فرض کنیم L1 مستقل از متن قطعی باشه و L2 منظم باشه ،آنگاه:
[tex]L_1\: \cap\: \: L_2[/tex] مستقل از متن قطعی خواهد بود.
همچنین زبانهای مستقل از متن قطعی و منظم هر دو تحت متمم گیری بسته هستند.پس:
[tex]L_1^-[/tex] هم مستقل از متن قطعی خواهد بود و [tex]L_2^-[/tex] هم که منظم هستش.
پس [tex]L_1^-\: \cap\: \: L_2^-[/tex] مستقل از متن قطعی خواهد بود.
پس [tex](L_1^-\: \cap\: \: L_2^-)^-[/tex] نیز مستقل از متن قطعی خواهد شد.
که معادل [tex]L_1\: \cup\: \: L_2[/tex] هستش.پس یعنی زبانهای مستقل از متن قطعی تحت اجتماع منظم بسته اند.
(۱۱ اردیبهشت ۱۳۹۵ ۱۲:۳۰ ق.ظ)Jooybari نوشته شده توسط: سلام. وقت بخیر.ممنون از پاسختون آقای جویباری.
به نظرم با تجذیه کردن به شکلی که زبان حاصل از اجتماع یا اشتراک یک زبان مستقل از متن قطعی با چند زبان منظم تشکیل بشه، زبان مستقل از متن قطعی خواهد بود. دلیل استدلالم اینه که دلیل غیرقطعی شدن ترکیب زبان های مستقل از متن اینه که همشون میخان از پشته استفاده کنن. ولی اگه فقط یکی از زبان ها با پشته کار داشته باشه میشه به روشی مشابه ترکیب زبانهای منظم، ماشین زبان ترکیبی رو ساخت و ساختار پشته رو با توجه به زبان مستقل از متن درنظر گرفت. البته این استدلال و نظر خودمه و خانم fatemeh69 توی این مباحث اطلاعات و مطالعات بیشتری دارن.
تو این لینک هم در مورد روش کشیدن DPDA اجتماع یک زبان منظم با یک زبان مستقل از متن قطعی گفته شده که باید بصورت موازی پیش بریم تا ساخته بشه:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close