تالار گفتمان مانشت

سوال کنکور علوم کامپیوتر ۹۰[attachment=971]

فکر میکنم گزینه سوم صحیح باشه
چون n-1 وضعیت برای تولید [tex]\left \{ a,b \right \}^{n-1}[/tex]لازم هست ویک وضعیت هم وضعیت اغازی برای[tex]\left \{ a,b \right \}^{n-1}[/tex] و یک وضعیت هم برای تولید [tex]\left \{ a,b \right \}^{*}[/tex]و [tex]\left \{ a \right \}[/tex] روی یال بین وضعیت اول و وضعیت اغازی [tex]\left \{ a,b \right \}^{n-1}[/tex] قرار میگیرد که در اینصورت به n+1 وضعیت نیاز است

بله نرگس جان درسته، میتونیم بگیم باید رشته هامون حداقل n حرفی باشه پس به n+1 وضعیت نیاز داریم.

اون *{a,b} هم به وضعیت اضافی نیاز نداره.

(12 مرداد 1390 10:06 ب.ظ)afagh1389 نوشته شده توسط: [ -> ]بله نرگس جان درسته، میتونیم بگیم باید رشته هامون حداقل n حرفی باشه پس به n+1 وضعیت نیاز داریم.

اون *{a,b} هم به وضعیت اضافی نیاز نداره.

میشه در مورد این جمله که گفتید: "اون *{a,b} هم به وضعیت اضافی نیاز نداره." بیشتر توضیح بدید؟!
من فکر میکنم برای [tex]\left \{ a,b \right \}^{*}[/tex]یک وضعیت باید در نظر بگیریم

نرگس جان به این خاطر که *{a,b} رو میتونیم با یک طوقه نشون بدیم و نیازی به یال نداره که بخواهیم وضعیت جدید ایجاد کنیم.

البته اگر مثلا زبان ما *{a,b} بود مجبور بودیم یک وضعیت ایجاد کنیم که روش طوقه رو بگذاریم ولی برای مثال بالا قبلا وضعیت ایجاد شده کافیه اول برای اون رشته n حرفی وضعیت‌ها رو ایجاد کنیم بعد طوقه رو روی حالت شروع بگذاریم.

---

مثلا اگر n=1 باشه اول اتوماتای مربوط به {L={a رو رسم میکنیم(با 2 وضعیت) بعد روی حالت شروع یک طوقه با برچسب a,b میگذاریم.

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

(12 مرداد 1390 08:36 ب.ظ)narges_r نوشته شده توسط: [ -> ]فکر میکنم گزینه سوم صحیح باشه
چون n-1 وضعیت برای تولید [tex]\left \{ a,b \right \}^{n-1}[/tex]لازم هست ویک وضعیت هم وضعیت اغازی برای[tex]\left \{ a,b \right \}^{n-1}[/tex] و یک وضعیت هم برای تولید [tex]\left \{ a,b \right \}^{*}[/tex]و [tex]\left \{ a \right \}[/tex] روی یال بین وضعیت اول و وضعیت اغازی [tex]\left \{ a,b \right \}^{n-1}[/tex] قرار میگیرد که در اینصورت به n+1 وضعیت نیاز است

اون حالت برای وضعیت آغازی قضیه اش چیه؟

(08 شهریور 1390 06:36 ب.ظ)ehsan_nekooee نوشته شده توسط: [ -> ]

(12 مرداد 1390 08:36 ب.ظ)narges_r نوشته شده توسط: [ -> ]فکر میکنم گزینه سوم صحیح باشه
چون n-1 وضعیت برای تولید [tex]\left \{ a,b \right \}^{n-1}[/tex]لازم هست ویک وضعیت هم وضعیت اغازی برای[tex]\left \{ a,b \right \}^{n-1}[/tex] و یک وضعیت هم برای تولید [tex]\left \{ a,b \right \}^{*}[/tex]و [tex]\left \{ a \right \}[/tex] روی یال بین وضعیت اول و وضعیت اغازی [tex]\left \{ a,b \right \}^{n-1}[/tex] قرار میگیرد که در اینصورت به n+1 وضعیت نیاز است

اون حالت برای وضعیت آغازی قضیه اش چیه؟

برای تولید n-1 رشته احتیاج به n وضعیت داریم پس برای تولید [tex]\left \{ a,b \right \}^{n-1}[/tex] احتیاج به n وضعیت است که من اسم یک وضعیت اضافی (وضیعیت اول برای تولید این عبارت)گذاشتم وضعیت اغازی وقبل از تمام این وضعیتها و وضعیت اغازی این عبارت به یک وضعیت دیگه برای تولید عبارات [tex]\left \{ a,b \right \}^{*}[/tex]و [tex]\left \{ a \right \}[/tex] نیازداریم