زمان کنونی: ۱۵ آبان ۱۴۰۳, ۰۸:۵۱ ق.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

بررسی بسته بودن خانواده ی زبان ها بر روی عملگر *

ارسال:
  

m-kafiyan پرسیده:

بررسی بسته بودن خانواده ی زبان ها بر روی عملگر *

یک سوالی داشتم
کلا خانواده ی زبان ها یعنی از همون خانواده ی زبان های منظم تا خانواده ی شمارش پذیر بازگشتی آیا همه تحت عملگر * بسته هستند یا نه؟
من فکر میکنم بسته باشند یعنی اون رویه ای که من بررسی کردم به نظرم بسته بودند اما دکتر کارگهی مقداری با ابهام در موردش صحبت کردند احساس میکنم نتیجه گیری من نادرست هست.
کسی میتونه جواب دقیق بدهد یا راهنمایی دقیقی من رو بکنه؟

۰
ارسال:
  

fatemeh69 پاسخ داده:

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 است)



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  حل و بررسی سوالات مدارمنطقی دکتری ۹۲ گرایش معماری nomad:D ۲۵ ۲۶,۴۱۴ ۲۰ بهمن ۱۴۰۲ ۱۰:۳۸ ق.ظ
آخرین ارسال: masoumeh97
  بررسی سوالات تخصصی دکتری هوش masoomeh_s ۱ ۲,۲۳۰ ۰۱ اسفند ۱۴۰۰ ۰۱:۰۹ ب.ظ
آخرین ارسال: vejdani
  کدام زبان برای هوش مصنوعی بهتر است؟ فرق بین زبان های هوش مصنوعی چیست؟ azam2075 ۳ ۶,۰۱۲ ۱۴ مهر ۱۴۰۰ ۰۷:۲۱ ب.ظ
آخرین ارسال: علیصا
  بررسی اعتبار یک مجله برای چاپ مقاله one hacker alone ۰ ۲,۲۶۳ ۲۱ اردیبهشت ۱۴۰۰ ۱۲:۲۶ ق.ظ
آخرین ارسال: one hacker alone
  تشریح تست همروندی - بررسی یکی از سوالات سال ۸۲ abji22 ۵ ۵,۱۴۱ ۰۲ دى ۱۳۹۹ ۱۱:۰۵ ق.ظ
آخرین ارسال: mohammadasadi1
  بررسی سوالات دکتری isoa ۲ ۲,۹۶۲ ۰۸ آبان ۱۳۹۹ ۰۸:۳۴ ب.ظ
آخرین ارسال: RoghayehAlipanahi
  اثبات بومی بودن sirvan.t ۸ ۵,۹۶۱ ۱۰ اسفند ۱۳۹۸ ۰۹:۴۶ ب.ظ
آخرین ارسال: WILL
  انجام پایان نامه برای داده کاوی استقرایی روی FIM ویافتن ARM با دوتا یا بیشتر CUDA GPU zaliabbass ۲ ۴,۳۸۶ ۰۶ اسفند ۱۳۹۸ ۰۸:۳۳ ب.ظ
آخرین ارسال: bankabzar
  بررسی وضعیت کار و درآمد گرایشهای مختلف. عزیز دادخواه ۱ ۲,۷۴۱ ۰۴ دى ۱۳۹۸ ۰۱:۱۲ ب.ظ
آخرین ارسال: marvelous
  نقش آفرینی بر روی پارچه در قدیم چگونه بوده است؟ maryamdolati ۰ ۷,۷۴۴ ۱۲ آذر ۱۳۹۸ ۰۵:۲۲ ب.ظ
آخرین ارسال: maryamdolati

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close