(۲۰ شهریور ۱۳۹۲ ۱۰:۲۶ ق.ظ)azk84 نوشته شده توسط:  چون تونستیم برای زبانمون NFA بکشیم، پس منظمه! :-)

دقیقا درسته، چون می تونیم برای یه NFA یا حتی DFA بکشیم پس منظمه، از شروط منظم بودن همین نمودارها بودند دیگه.

و اینکه به صورت صریح گفتم NFA یا DFA چون مطابق الگوریتم هایی که داریم می تونیم به یکدیگر تبدیل کنیم.

(۲۰ شهریور ۱۳۹۲ ۱۲:۱۶ ب.ظ)poldasht نوشته شده توسط:  

(20 شهریور ۱۳۹۲ ۱۰:۲۶ ق.ظ)azk84 نوشته شده توسط:  چون تونستیم برای زبانمون NFA بکشیم، پس منظمه! :-)

دقیقا درسته، چون می تونیم برای یه NFA یا حتی DFA بکشیم پس منظمه، از شروط منظم بودن همین نمودارها بودند دیگه.

و اینکه به صورت صریح گفتم NFA یا DFA چون مطابق الگوریتم هایی که داریم می تونیم به یکدیگر تبدیل کنیم.

خب اینکه میشه nfa و dfa برای منظم کشید که حرفی توش نیست، ولی منکه سر جلسه کنکور وقت ندارم بشینم nfa بکشم.
مخصوصا واسه سوال اول که اصلا nfa به ذهنم نمیرسه
میخوام بدونم چه جور باید این سوالها رو تحلیل کرد که موقع تست، وقتی یه زبان رو میبینیم، بفهمیم منظمه یا غیر منظمه
مثل تحلیل های زیر:
متناهی بودن زبان
سیگما بودن زبان
زبان نامتناهی باشه ولی بین تعداد عناصر زبان ارتباطی نباشه
واز این جور چیزها

از شما دوست عزیز هم تشکر میکنم که در بحث شرکت کردید

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

(20 شهریور ۱۳۹۲ ۱۰:۲۶ ق.ظ)azk84 نوشته شده توسط:  ببینید، همونطور که دوستمون Nana2010 گفت، برای اولین زبان، اگر n = 0 رو در نظر بگیریم، مجموعه‌ی زبان ما برابر سیگما استار میشه. بنابراین برای n های بزرگ‌تر مجموعه زبان ما تغییر نمی‌کنه، چون دیگه بزرگ‌تر از سیگما استار نمیتونه بشه. سیگما استار هم می‌دونیم که منظمه.


دومین زبان عملاً شامل تمام رشته‌هایی میشه که سمت چپشون حداقل ۱۰۰تا a و سمت راستشون حداقل ۱۰۰تا b باشه. بین این دو هر چیزی می‌تونه باشه، بنابراین اگه سمت چپ ۱۰۰۰تا a باشه و سمت راست هم ۱۰۰۰ تا b، باز هم چون شرط حداقل ۱۰۰ تا a در چپ و ۱۰۰تا b در راست رعایت شده جزو این زبان هست. منظورم اینه که برای یک رشته ما فقط کافیه چک کنیم ببینیم آیا دو طرف ۱۰۰تا a و b هست یا نه. اگه بود رشته عضوی از زبان ما هست و اگه نبود نیست.
حالا که فقط کافیه شرط ۱۰۰ تا رو چک کنیم، عبارت منظم زبانمون رو میشه به شکل دیگه‌ای نوشت: a^100 (a+b)* b^100. می‌بینیم که چون زبان ما عبارت منظم داره پس منظمه!
البته میشه به جای عبارت منظم براش NFA کشید: از محل شروع (حالت ۱) با یک a میره حالت ۲، با یک a دیگه میره حالت ۳ و به همین ترتیب ۱۰۰ بار با a میره به حالت بعدی تا برسه به حالت ۱۰۱/ اونجا حالت ۱۰۱ با a و b میره به خودش. همچنین با b میره به حالت ۱۰۲/ از حالت ۱۰۲ با b میره به ۱۰۳ و به همین ترتیب ۱۰۰ بار با b میره به بعدی تا حالت ۲۰۲/ حالت ۲۰۲ که آخرین حالتمونه فایناله! چون تونستیم برای زبانمون NFA بکشیم، پس منظمه! :-)

ممنون از دوست خوبم azk84
در مورد زبان اولی من قانع نشدم؛ یعنی برای یک حالت خاص که n=0 بود ما دیدیم که رشتمون میشه w که همون سیگما هست و چون n هر عدد دیگه ای باشه دیگه بزرگتر از سیگما نمیشه پس منظمه ؟؟؟
اگر در مورد زبان اولی اشتباه برداشت کردم، لطفا منو راهنمایی کنید.

زبان دومی رو فهمیدم و اینجور نتیجه گیری کردم که:
با اینکه n میتونه عددی نامتناهی باشه ولی فقط ۱۰۰ تای اول و آخر رشته ترکیب خاص ما هستند و هر چیزی که بین اینها قرار بگیرن با رشته w که همون سیگما هست قاطی میشه و دیگه برامون اهمیتی نداره.
و اگر شرط n>=100 را با شرط n>=0 در نظر بگیریم اونوقت دیگه این زبان منظم نیست. درسته ؟

باتشکر

ببینید، اون شرطی که برای زبان می‌ذاره که مثلاً [tex]a^{n}wb^{n}[/tex] با شرط n>=100 به این معنی هستش که تمام رشته‌های به شکلهای [tex]a^{100}wb^{100}[/tex] و [tex]a^{101}wb^{101}[/tex] و [tex]a^{102}wb^{102}[/tex] و ... عضو زبان ما هستند. به عبارتی اجتماع تمام این مجموعه رشته‌ها میشه کل مجموعه‌ی زبان ما.

در سؤال اول ([tex]a^{n}b^{n}w[/tex] با شرط n >= 0)، چون فقط خود [tex]a^{0}b^{0}w[/tex] به تنهایی میشه سیگما استار، دیگه اضافه شدن سایر رشته‌ها به شکل‌های [tex]a^{1}b^{1}w[/tex] و [tex]a^{2}b^{2}w[/tex] و ... به این مجموعه‌ی سیگما استار باز هم نتیجه‌اش میشه سیگما استار (اجتماع سیگما استار با هر مجموعه‌ای باز هم میشه سیگما استار). بنابراین کلاً زبان ما میشه سیگما استار که یک زبان منظم هستش :-)

توی کنکور همیشه سعی کنین تا حد امکان بفهمین کل زبان چه شکلی میشه. لازم نیست همون اول به DFA و NFA و ایناش فکر کنین. حتی اگه به DFA و NFA فکر کردین لازم نیست که کامل رسمش کنین تا مطمئن شین وجود دارند و فقط کافیه تا جایی برین که مطمئن شین وجود دارن. مثلاً واسه یک زبان اگه از یک چیزی (مثلاً کاراکتر a) می‌تونست یه تعداد نامحدود بیاد و در عین حال نیاز بود که این تعداد حتماً نگهداری بشه، در این صورت زبان منظم نیست. به عنوان مثال توی [tex]a^{n}b^{n}[/tex] با شرط n>=0 (با سؤال شما فرق داره هاا)، هر جور حساب کنین ما نیاز داریم تعداد دفعاتی که a اومده رو نگه داریم تا تعداد دفعات b همون تعداد بشه. در عین حال هم بر خلاف سؤال شما [tex]a^{1}b^{1}[/tex] و [tex]a^{2}b^{2}[/tex] و ... زیرمجموعه‌ی [tex]a^{0}b^{0}[/tex] نیستند. پس حتماً زبان ما منظم نیست.

امیدوارم بهتر از دفعه‌ی پیش تونسته باشم توضیح بدم :-)

ممنون از تمام دوستان

حس میکنم که موضوع را فهمیده باشم، هرچند یه تعداد دیگه از این عبارات منظم سوال داشتم ولی اگه تونستم با این توضیحاتی که شما دادید حل بکنم دیگه نمیپرسم. مگه اینکه خیلی خنگ باشم و مجبور باشم بازم بپرسم

یه نتیجه گیری از سوال و جواب میکنم (البته فقط نظر خودمه) برای اینکه کلیت موضوع را بفهمم
اول اینکه هدف من از طرح سوال، این نبود که دوستان براش گرامر یا nfa یا عبارت منظم و ... بگن. هدف این بود که به صورت تحلیلی، منظم بودن و یا نبودن زبان را بفهمیم. یه جورایی کنکوری حل کنیم

مثلا وقتی میخواهیم ثابت کنیم یه زبان مثل [tex]a^{n\n} b^{n\n}[/tex] نامنظمه، خب چیزی که واضحه اینه که نمیتونم بگم چون برای این نمیشه nfa کشید پس نامنظمه. باید چرایی رو بررسی کنیم. چرا نمیشه برای این زبان nfa کشید؟؟؟
و دلیلش اینه که زبان منظم یا بهتر بگیم dfa و nfa حافظه ندارن که بخوان تعداد a را نگه دارند تا بعد در مورد تعداد b تصمیم گیری کنند یا به عبارتی دیگر چون تعداد a و b به هم مرتبط و نامتناهی هم هستد پس زبان نامنظمه.

یا وقتی سوال میشه که مثلا چرا زبان [tex]\left \{ a^{n\n} b^{n\n} w | n\geq 0 ,w \epsilon \\\sum^* \right \}[/tex] منظمه، مسلما من نه میتونم واسش nfa بکشم و نه عبارت منظم بنویسم.
بلکه باید یه تحلیلی براش بیارم که این عبارت میتونه منظم باشه

نتایجی که گرفتم
سوال۱: [tex]\left \{ a^{n\n} b^{n\n} w | n\geq 0 ,w \epsilon \\\sum^* \right \}[/tex]
در اینجا زمانی که به n هر عددی بدهیم مثلا ۰ زبان به شکل [tex]a^{0\n} b^{0\n} w = w[/tex] در میاد که این زبان همون سیگمای خودمونه.
وقتی n هر عدد دیگه ای باشه، از [tex]a^{1\n} b^{1\n} w = abw[/tex] گرفته تا [tex]a^{n\n} b^{n\n} w[/tex] به علت داشتن سیگمایی که در آخر رشته هست، میتونیم رشته های [tex]a^{n\n} b^{n\n} [/tex] اول را با سیگما بسازیم.
یعنی اجتماع a و b های اول با سیگما همون سیگما میشه. یه جورایی رشته اول قاطی میشه با سیگما.
و سیگما هم که منظمه.

سوال۲: [tex]\left \{ a^{n\n} w b^{n\n} | n\geq 100 ,w \epsilon \\\sum^* \right \}[/tex]
اینجا هم اولین n ممکن رو اگه ببینیم متوجه میشیم که زبان به صورت [tex] a^{100\n} w b^{100\n} [/tex] میشه. خب واضحه که این زبان منظمه چون تعداد a و b هرچند به هم مربوط هستند ولی به دلیل اینکه تعدادشون متناهیه و رشته وسط هم خطری برای منظم بودن نداره پس زبان به ازای n=100 منظمه.
حالا اگر مقدار ۱۰۰ را افزایش بدهیم یعنی
[tex] a^{101\n} w b^{101\n} [/tex]

[tex] a^{1000\n} w b^{1000\n} [/tex]

[tex] a^{n\n} w b^{n\n} [/tex]
شاید رشته زبان بزرگتر شده ولی نکته ای که در اون نهفته است اینه رشته های بالا الگویی از رشته [tex] a^{100\n} w b^{100\n} [/tex] هستند . در تمامی رشته های حتما [tex] a^{100\n} [/tex] در اول رشته و [tex]b^{100\n} [/tex] در آخر رشته قرار دارد و وسط رشته هم هر چیزی که هست با رشته w که همون سیگما هست میشه ساخت.
البته یه چیزی تو ذهنم هست که درست نمیتونم بیان کنم شرمنده

پس این زبان هم منظمه.
و بر خلاف تصور من که فکر میکردم اگر این زبان به صورت
[tex]\left \{ a^{n\n} w b^{n\n} | n\geq 0 ,w \epsilon \\\sum^* \right \}[/tex]
باشه ، زبان نامنظم میشه ولی الان با تعاریفی که شد این زبان هم منظمه. (با اینکه بعید میدونم اینو اشتباه گفته باشم ولی اگه اشتباه بود تذکر بدید). چون بازهم این زبان چیزی نیست جز سیگما و علنا a و b اول و آخر رشته با w وسط قاطی میشن و با سیگما قابل ساخته.

امیدوارم موضوع رو خوب فهمیده و جمع بندی کرده باشم
از دوستانی هم که در بحث شرکت کردند ممنون.
فقط نمیدونم چرا این دکمه های رای مثبت کار نمیکنه که بهتون چندتا مثبت بدم.
و چون اولین پستم در مانشت بود و خیلی جواب و سوال و نقل قول این انجمن برام گیج کننده شده بود.

ببینید در صورت سوال ما میتونیم برای این زبان یک عبارت منظم بنویسیم:
مثلا برای a^nمیتونیم از قاعده ی A->aA|landaاستفاده کنیم...برای ترمینال b نیز به همین صورت...وزبان wنیز میتونه به صورت هر ترکیبی از aیاbنوشته شود...(a|b) به توان *

نهایتا الحاق این زبانها میتونند کل این زبان رو بوجود بیارند...این نکات برای اثبات منظم بودن زبان کافیست..امیدوارم منظورمو رسونده باشم..

(۱۹ شهریور ۱۳۹۲ ۱۱:۱۳ ب.ظ)sahar_2000 نوشته شده توسط:  ببینید در صورت سوال ما میتونیم برای این زبان یک عبارت منظم بنویسیم:
مثلا برای a^nمیتونیم از قاعده ی A->aA|landaاستفاده کنیم...برای ترمینال b نیز به همین صورت...وزبان wنیز میتونه به صورت هر ترکیبی از aیاbنوشته شود...(a|b) به توان *

نهایتا الحاق این زبانها میتونند کل این زبان رو بوجود بیارند...این نکات برای اثبات منظم بودن زبان کافیست..امیدوارم منظورمو رسونده باشم..

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

(۲۰ شهریور ۱۳۹۲ ۰۴:۰۰ ب.ظ)zimenswall نوشته شده توسط:  مثلا وقتی میخواهیم ثابت کنیم یه زبان مثل [tex]a^{n\n} b^{n\n}[/tex] نامنظمه، خب چیزی که واضحه اینه که نمیتونم بگم چون برای این نمیشه nfa کشید پس نامنظمه. باید چرایی رو بررسی کنیم. چرا نمیشه برای این زبان nfa کشید؟؟؟
و دلیلش اینه که زبان منظم یا بهتر بگیم dfa و nfa حافظه ندارن که بخوان تعداد a را نگه دارند تا بعد در مورد تعداد b تصمیم گیری کنند یا به عبارتی دیگر چون تعداد a و b به هم مرتبط و نامتناهی هم هستد پس زبان نامنظمه.

دقیقاً ;-)

(۲۰ شهریور ۱۳۹۲ ۰۴:۰۰ ب.ظ)zimenswall نوشته شده توسط:  در اینجا زمانی که به n هر عددی بدهیم مثلا ۰ زبان به شکل [tex]a^{0\n} b^{0\n} w = w[/tex] در میاد که این زبان همون سیگمای خودمونه.

یک نکته این که سیگما مجموعه‌ی کل کاراکترها هستش و سیگما استار مجموعه‌ی کل رشته‌های قابل تولید با کاراکترهای درون مجموعه‌ی سیگما. شما اشتباهاً به جای سیگما استار اصطلاح سیگما رو به کار می‌برین :-).

(۲۰ شهریور ۱۳۹۲ ۰۴:۰۰ ب.ظ)zimenswall نوشته شده توسط:  وقتی n هر عدد دیگه ای باشه، از [tex]a^{1\n} b^{1\n} w = abw[/tex] گرفته تا [tex]a^{n\n} b^{n\n} w[/tex] به علت داشتن سیگمایی که در آخر رشته هست، میتونیم رشته های [tex]a^{n\n} b^{n\n} [/tex] اول را با سیگما بسازیم.
یعنی اجتماع a و b های اول با سیگما همون سیگما میشه. یه جورایی رشته اول قاطی میشه با سیگما.
و سیگما هم که منظمه.

راستش من دقیق منظورتونو متوجه نشدم. حرف من (نمیدونم پستم چی شد، ولی قبل پست شما بود !؟!!) این بود که چون برای n=0 کل سیگما استار تولید شده، هر چیزی به هر شکلی که باز هم برای nهای بزرگ‌تر تولید بشه باز هم زیرمجموعه‌ی سیگما استار هستش و چیز جدیدی به مجموعه‌ی زبان ما نمیتونن اضافه کنند. بنابراین کل زبان ما میشه سیگما استار.

(۲۰ شهریور ۱۳۹۲ ۰۴:۰۰ ب.ظ)zimenswall نوشته شده توسط:  و بر خلاف تصور من که فکر میکردم اگر این زبان به صورت

باشه ، زبان نامنظم میشه ولی الان با تعاریفی که شد این زبان هم منظمه. (با اینکه بعید میدونم اینو اشتباه گفته باشم ولی اگه اشتباه بود تذکر بدید). چون بازهم این زبان چیزی نیست جز سیگما و علنا a و b اول و آخر رشته با w وسط قاطی میشن و با سیگما قابل ساخته.

درسته :-)

سلام.من دو تا سوال برام پیش اومد:
۱- A^2B^2 اجتماعش با W میشه رشته های ما؟
۲-اگر زبان A^n B^n و n>=0 باشه و A,B={1,0}star باشه منظمه؟
زبان سوال ۶۲ سال ۸۷ هم میگید دلایل منظم بودن زبان هارو؟
ممنون.