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

تشخیص زبان های مستقل از متن

ارسال:
  

Ametrine پرسیده:

Question تشخیص زبان های مستقل از متن

سلام

من هنوزم نمیتونم زبان های مستقل از متن رو خوب تشخیص بدم.
لطفاً رو این سه تا زبان توضیح بدید.

[تصویر:  CF.jpg]


۳
ارسال:
  

moloodi پاسخ داده:

RE: تشخیص زبان های مستقل از متن

یک فرمول داره که بچه ها فک کنم زیاد ازش استفاده کنن ولی من چون از فرمول یاد گرفتن خوشم نمیاد اصلا از اون حل نمیکنم .

بنظرم بهترین راه فک کردن به ساخت ماشین پشته ای برای زبانه (نه اینکه ماشین و طراحی کنین فقط به ممکن بودن طراحیش فک کنید البته اینکه ماشین می تواند غیر قطعی هم باشه خیلی مهمه باید حواستون جم باشه)

مثلا زبان اول :
ماشین اگه اول b ببینه دیگه فقط b می تونه بیاد.
اما اگه اول a ببینه باید تعدادشون و تو پشته ذخیره کنه حالا از اینجا به بعد باید از عدم قطعیت کمک بگیریم یعنی با توجه به اینکه b وسط می تواند نیاید، باید به صورت غیر قطعی از یکجایی شروع به match کردن a های ورودی کنیم نه ذخیره، ولی اگه b دیدیم دیگه می تونیم قطعی تصمیم بگیریم.

زبان دوم و میشه بصورت قطعی پذیرفت من خودم یکم روش فک کردم تا مطمعن شدم زود نتونستم قطعی بودنشو تشخیص بدم، اول فک کردم غیر قطعیه.
داستانشم اینه که با دیدن b در ابتدا دیگه فقط میتونیم b ببینیم ولی اگه a دیدیم تعدادشو ذخیره می کنیم حالا اگه b دیدیدیم (شاید اصلا نبینیم که رشته در این حالت قبول است) شروع به match کردن می کنیم در این مرحله حالات زیر ممکنه رخ بدن ولی همشون قطعین :
- b ها match نمیشن و رشته تمام می شود : در این حالت رشته قبول است
- اگه قبل از اینکه همه b ها match بشن a ببینیم : قبول نیست
- اگه بعد از match شدن ، a ببینیم دیگه کافیه فقط ترتیب a و b های ادامه درست باشه .
- اگه b ها بیشتر از a ها بودن دیگه در ادامه فقط می تونه b باشه.

شاید بصورت تایپی نشه حق مطلب و ادا کرد ولی من اینطوری عمل میکنم.

سومی هم شبیه همینا تحلیل میشه کرد.
من فک کنم قطعی یا غیر قطعی بودن اینا مد نظر بوده چون مستقل از متن بودنشون واسه بچه ها راحته (با همون فرموله)

۲
ارسال:
  

ریحان پاسخ داده:

RE: تشخیص زبان های مستقل از متن

وای چه سخته سوالش...هول کردم...منم نمیفهمم

ارسال:
  

moloodi پاسخ داده:

RE: تشخیص زبان های مستقل از متن

(۳۰ دى ۱۳۹۳ ۰۲:۳۶ ق.ظ)ریحان نوشته شده توسط:  وای چه سخته سوالش...هول کردم...منم نمیفهمم
قطعی یا غیر قطعی بودنش به نظرم یک مقدار تمرکز بیشتری نسبت به سوالای معمول میخواد.
یافتن تمامی ارسال‌های این کاربر

ارسال:
  

fatemeh69 پاسخ داده:

RE: تشخیص زبان های مستقل از متن

(۳۰ دى ۱۳۹۳ ۰۳:۱۹ ق.ظ)moloodi نوشته شده توسط:  
(30 دى ۱۳۹۳ ۰۲:۳۶ ق.ظ)ریحان نوشته شده توسط:  وای چه سخته سوالش...هول کردم...منم نمیفهمم
به نظر من کاملا حق دارید سطح سوال از حد این آزمون های بدرد نخوره پارسه که ما می دیم بالاتره.

واسه تشخیص مستقل از متن بودن کافیه چک کنید که توان ها به فرم پرانتزی هستند یا نه و این که یه توان دو تا مقایسه نداشته باشه
مثلا زبان [tex]a^nb^ma^nb^m[/tex] اگه n رو پرانتز و m رو آکولاد فرض کنیم فرم زبانش این شکلیه {(}) که به فرم پرانتزی صحیح نیست
امام مثلا زبان اولی که تو عکس این تاپیک گذاشتن چون q,s فقط یه بار ظاهر شدن که مقایسه نمیشن و فقط p هست که مقایسه می شه و با در نظر گرفتن P به عنوان پرانتز زبانش می شه () که فرم صحیحه همه ی زبان های این عکس تاپیک به فرم صحیح پرانتزی هستن

یا مثلا تو بعضی زبان ها باید چک کنیم که هر عدد فقط یه بار مقایسه بشه مثلا زبان [tex]a^nb^ma^nb^{m n}[/tex] چون عدد n یه بار یا a های بخش دوم مقایسه شده یه بار با b های بخش دوم پس مستقل از متن نیست اما تمام زبان هایی که تو عکس این تاپیک گذاشتن همه ی اعداد فقط یه مقایسه می شن

پس نتیجه می گیریم همشون مستقل از متن هستند


اما برای تشخخیص قطعی بودن
باید هر بار چک کنید که p یا q یا s یا r اگه صفر بشن چی می شه
آیا ما از قطعیت در میایم یا نه
که دوستمون کامل توضیح دادن
یافتن تمامی ارسال‌های این کاربر

۰
ارسال:
  

ریحان پاسخ داده:

RE: تشخیص زبان های مستقل از متن

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

ارسال:
  

moloodi پاسخ داده:

RE: تشخیص زبان های مستقل از متن

(۱۱ بهمن ۱۳۹۳ ۰۷:۳۴ ب.ظ)ریحان نوشته شده توسط:  دوستان چرا زبانی که در رشته ی w تعداد رشته های a مخالفb است مستقل از متن قطعیه؟ چطوری میشه توی پشته؟
خب ما که نمیدونیم اول a میاد یا b که ببینیم برای اومدن a علامت در پشته بذاریم یا برداریم؟ یا همینظورم واسه b؟ که بعد اگه بفهمیم a ها بیشترن یا b ها...

می تونیم از یکسری نماد دیگه استفاده کنیم که نشان دهنده اون حالات باشن.
مثلا :
a دیدیم و پشته خالی بود A بذار.
b دیدیم و پشته خالی بود B بذار.
a دیدی و A روی پشته بود یک A دیگه روش بذار بشه AA.
b دیدی و روی پشته B بود یک B دیگه روش بذار بشه BB.
a دیدی و روی پشته B بود اونو از تاپ پشته حذف کن.
b دیدی و تاپ پشته A بود اونو از تاپ پشته حذف کن.
یافتن تمامی ارسال‌های این کاربر

۰
ارسال:
  

ریحان پاسخ داده:

RE: تشخیص زبان های مستقل از متن

پس چرا کتاب جبل عاملی گفته این غیر قطعیه؟ وای خدا...چیکار کنم؟ پسww^r هم میشه قطعی که...Confused

ارسال:
  

moloodi پاسخ داده:

RE: تشخیص زبان های مستقل از متن

(۱۲ بهمن ۱۳۹۳ ۰۱:۰۳ ق.ظ)ریحان نوشته شده توسط:  پسww^r هم میشه قطعی که...Confused
نه دیگه . واسه زبان ww^r چون نمیدونیم وسط کجاس بصورت قطعی نمی تونیم تصمیم بگیریم باید از یکجایی همینطوری شانسی بگیم اینجا وسطه بعد بریم ببینم درست بوده یا نه.
یافتن تمامی ارسال‌های این کاربر

۰
ارسال: #۱۰
  

ریحان پاسخ داده:

RE: تشخیص زبان های مستقل از متن

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



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  چرا مستقل از متنه؟ Wa^nb^mW^R poldasht ۱۱ ۳,۴۳۸ ۱۴ بهمن ۱۳۹۳ ۰۹:۱۰ ب.ظ
آخرین ارسال: ss.hoseini
  خواص مستقل از متن maryam.roshan ۳ ۲,۲۸۷ ۱۲ بهمن ۱۳۹۳ ۱۱:۰۱ ب.ظ
آخرین ارسال: fatemeh69
  تشخیص قطعی بودن ۴ زبان مستقل از متن MR.oracle ۹ ۳,۹۵۱ ۱۲ بهمن ۱۳۹۳ ۱۲:۲۳ ب.ظ
آخرین ارسال: ریحان
  چرا عکس نقیض لم تزریق مستقل از متن نشان دهنده نامنظم بودنه؟ ریحان ۷ ۲,۳۶۸ ۱۲ بهمن ۱۳۹۳ ۱۲:۱۳ ب.ظ
آخرین ارسال: ریحان
  چرا n(a)=!n(b) مستقل از متن قطعیه؟ ریحان ۸ ۲,۵۳۸ ۱۱ بهمن ۱۳۹۳ ۱۱:۰۲ ب.ظ
آخرین ارسال: ریحان
  آیا این زبان مستقل از متن است؟؟ K<=max(i,j) Imankhani ۸ ۲,۹۵۴ ۱۱ بهمن ۱۳۹۳ ۰۷:۴۷ ب.ظ
آخرین ارسال: ریحان
  تشخیص اجتماع و اشتراک یک زبان جساس به متن با مستقل از متن یا منظم maryam.roshan ۱ ۱,۶۰۳ ۱۱ بهمن ۱۳۹۳ ۱۲:۴۳ ق.ظ
آخرین ارسال: fatemeh69
  نحوه تشخیص زبان های خطی arefeh.hp ۷ ۴,۸۹۸ ۰۹ بهمن ۱۳۹۳ ۰۱:۰۵ ق.ظ
آخرین ارسال: nazanin2020
  آیا مستقل از متن قطعی است؟${a^mb^mc^n:0≤m≤n≤۲m\}$ archer22 ۳ ۱,۸۴۱ ۰۷ بهمن ۱۳۹۳ ۰۹:۰۲ ب.ظ
آخرین ارسال: Hamid_0311
  مشکل در تشخیص ویژگی های زبان مستقل از متن قطعی mostafa2012 ۴ ۲,۳۱۹ ۰۶ بهمن ۱۳۹۳ ۰۲:۳۲ ب.ظ
آخرین ارسال: mostafa2012

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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