۰
subtitle
ارسال: #۱
  
بررسی بسته بودن خانواده ی زبان ها بر روی عملگر *
یک سوالی داشتم
کلا خانواده ی زبان ها یعنی از همون خانواده ی زبان های منظم تا خانواده ی شمارش پذیر بازگشتی آیا همه تحت عملگر * بسته هستند یا نه؟
من فکر میکنم بسته باشند یعنی اون رویه ای که من بررسی کردم به نظرم بسته بودند اما دکتر کارگهی مقداری با ابهام در موردش صحبت کردند احساس میکنم نتیجه گیری من نادرست هست.
کسی میتونه جواب دقیق بدهد یا راهنمایی دقیقی من رو بکنه؟
کلا خانواده ی زبان ها یعنی از همون خانواده ی زبان های منظم تا خانواده ی شمارش پذیر بازگشتی آیا همه تحت عملگر * بسته هستند یا نه؟
من فکر میکنم بسته باشند یعنی اون رویه ای که من بررسی کردم به نظرم بسته بودند اما دکتر کارگهی مقداری با ابهام در موردش صحبت کردند احساس میکنم نتیجه گیری من نادرست هست.
کسی میتونه جواب دقیق بدهد یا راهنمایی دقیقی من رو بکنه؟
۰
ارسال: #۲
  
RE: بررسی بسته بودن خانواده ی زبان ها بر روی عملگر *
منظم ها که بسته اند کافیه از روی nfa آن یک یال با لاندا از حالات فاینال به حالات شروع بفرستیم و یال لاندا از حالات شروع به حالات فاینال بفرستیم
در cf ها با اضافه کردن قانون ss->ss|lambda به گرامر زبان L ، گرامز *L را خواهیم و گرامر جدید باز هم cf است
در r.e ها هم با اضافه کردن قانون ss->ss|lambda به گرامر زبان L ، گرامز *L را خواهیم و گرامر جدید باز هم از نوع صفر و *L از نوع r.e است
اما در cs ها می تونیم قاعده ی s-->ss را اضافه کنیم اما نم یتوانیم قاعده ی لامبدا را اضافه کنیم چون از cs بودن می افته اما اگر قاعده ی لاند رو نذاریم چیزی رو از دست نمی دیم به جز یه رشته ی لاندا. در غیر ایون صورت برای تولید رشته های l که همون قاعده یه ای گرامر اولیه کافیه برای تولید رشته های L^2 اول یه قاعده ی s-->ss می ریم بعد از اون قاعده ی های گرامر اولیه استفاده می کنیم برای L^k اول k-1 بار از قاعده ی s-->ss استفاده می کنیم بعد از اون قاعده های گرامر اولیه استفاده می کنیم و از کل *L فقط یه رشتهلاندا رو نمی تونیم تولید کنیم که اونم مشکلی نداره چون یه تبصره داریم که می گه اگه گرامر cs ای همه ی رشته های یه زبان رو به جز لاندا رو تولید کنه زبان معادل اون گرامر (چه با لاندا چه بی لاندا) باز cs است.
پس برای *L هم می تونیم گرامر cs بنویسیم که عبارتست از گرامر cs مربوط به L به اضافه ی قاعده ی s-->ss (پس *Lهم cs است)
در cf ها با اضافه کردن قانون ss->ss|lambda به گرامر زبان L ، گرامز *L را خواهیم و گرامر جدید باز هم cf است
در r.e ها هم با اضافه کردن قانون ss->ss|lambda به گرامر زبان L ، گرامز *L را خواهیم و گرامر جدید باز هم از نوع صفر و *L از نوع r.e است
اما در cs ها می تونیم قاعده ی s-->ss را اضافه کنیم اما نم یتوانیم قاعده ی لامبدا را اضافه کنیم چون از cs بودن می افته اما اگر قاعده ی لاند رو نذاریم چیزی رو از دست نمی دیم به جز یه رشته ی لاندا. در غیر ایون صورت برای تولید رشته های l که همون قاعده یه ای گرامر اولیه کافیه برای تولید رشته های L^2 اول یه قاعده ی s-->ss می ریم بعد از اون قاعده ی های گرامر اولیه استفاده می کنیم برای L^k اول k-1 بار از قاعده ی s-->ss استفاده می کنیم بعد از اون قاعده های گرامر اولیه استفاده می کنیم و از کل *L فقط یه رشتهلاندا رو نمی تونیم تولید کنیم که اونم مشکلی نداره چون یه تبصره داریم که می گه اگه گرامر cs ای همه ی رشته های یه زبان رو به جز لاندا رو تولید کنه زبان معادل اون گرامر (چه با لاندا چه بی لاندا) باز cs است.
پس برای *L هم می تونیم گرامر cs بنویسیم که عبارتست از گرامر cs مربوط به L به اضافه ی قاعده ی s-->ss (پس *Lهم cs است)
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close