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

تشخیص قطعی بودن ۴ زبان مستقل از متن

ارسال:
  

MR.oracle پرسیده:

تشخیص قطعی بودن ۴ زبان مستقل از متن

سلام میشه بگید زبان های توی عکس مستقل از متن قطعی هستند یا نه ..اگه میشه یه توضیح کوچک هم بدید تا بفهمم ممنون میشم
[تصویر:  324308_bf7ccbd384dea39124cedea30a17ca29.jpg]


فایل‌(های) پیوست شده

۴
ارسال:
  

moloodi پاسخ داده:

RE: تشخیص قطعی بودن زبان مستقل از متن

قسمت اول این سوال جالبه تعداد حروف a ,b برابر تعداد حروف رشته. این زبان یعنی تهی چون فقط شرط برای تهی صادقه.
قسمت آخر هم که کاملا مشخص هیچ عدم قطعیتی در ماشین وجود نداره و ما باید تعداد a , b را برابر داشته باشیم.
قسمت دوم و نیگاه کنید زبان از اجتماع دو زبان دیگر تشکیل شده یعنی رشته هایی که یا برای زبان اول هستند یا برای زبان دوم که با دیدن یا ندیدن a در ابتدا می توان تشخیص داد کدام حالت باید بررسی شود پس باز هم عدم قطعیت نداریم.
قسمت سوم یکم جالب تره البته از روی شکل من برداشت می کنم که الحاق دوزبان است که زبان دوم فقط یک عضو دارد. کاری که اینجا می توان انجام داد ابتدا از اول رشته شروع می کنیم و باید یک رشته عضو زبان اول ببینیم سپس تعدادی ظاهرا a مثلا ۱۰ تا. برای زبان اول چون دو رشته با حرف c جدا شده اند و c عضو الفبای زبان نیست ما با دیدن c بطور قطع میتوانیم بگیم که به وسط رشته رسیده ایم و وقت چک کردن معکوس آنچه که خواهیم دید با آنچه که دیده ایم می باشد. بعد از حصول اطمینان از این قسمت نوبت به دیدن ۱۰ a متوالی است. تمام مراحل انجام بصورت قطعی است و اما و اگر ندارد.


در باره زبان دوم اگر شکل به این صورت تغییر کند عدم قطعیت در پذیرش داریم
[tex]\{a^nb^{3m}\: :\: n,m\ge0\}\cup\{b^{2k}\: :\: k\ge0\}[/tex]

۰
ارسال:
  

MR.oracle پاسخ داده:

Re: RE: تشخیص قطعی بودن زبان مستقل از متن

(۱۱ دى ۱۳۹۳ ۰۶:۰۹ ب.ظ)moloodi نوشته شده توسط:  قسمت اول این سوال جالبه تعداد حروف a ,b برابر تعداد حروف رشته. این زبان یعنی تهی چون فقط شرط برای تهی صادقه.
قسمت آخر هم که کاملا مشخص هیچ عدم قطعیتی در ماشین وجود نداره و ما باید تعداد a , b را برابر داشته باشیم.
قسمت دوم و نیگاه کنید زبان از اجتماع دو زبان دیگر تشکیل شده یعنی رشته هایی که یا برای زبان اول هستند یا برای زبان دوم. حال با توجه به اینکه دو زبان قواعد متفاوتی دارند اینجا باید از عدم قطعیت استفاده کنیم کاری که اینجا می توان انجام داد این است که برای هر یک از زبان ها پذیرنده طراحی کرد و حالت شروع آن ها را با گذر تهی به یکدیگر مربوط ساخت به عبارت دیگر رشته ورودی معلوم نیست از کدام مسیر می رود ولی از هرکدام که برود و پذیرفته شود قبول است.
قسمت سوم یکم جالب تره البته از روی شکل من برداشت می کنم که الحاق دوزبان است که زبان دوم فقط یک عضو دارد. کاری که اینجا می توان انجام داد ابتدا از اول رشته شروع می کنیم و باید یک رشته عضو زبان اول ببینیم سپس تعدادی ظاهرا a مثلا ۱۰ تا. برای طبان اول چون تو رشته با حرف c جدا شده اند و c عضو الفبای زبان نیست ما با دیدن c بطور قطع میتوانیم بگیم که به وسط رشته رسیده ایم و وقت چک کردن معکوس آنچه که خواهین دید با آنچه که دیده ایم می باشد. بعد از حصول اطمینان از این قسمت نوبت به دیدن ۱۰ a متوالی است. تمام مراحل انجام بصورت قطعی است و اما و اگر ندارد.
سلام خیلی لطف کردید وقت گذاشتید و جواب دادید.خیلی خیلی ممنون
توی قسمت دوم میتونیم بگیم اگر a اومد برو قسمت بالا تساوی با b رو چک کن اگر هم همون اول b اومد برو ماشین پایین تعداد زوج b چک کن؟اگه این کارو کنیم قطعی نیست؟

۰
ارسال:
  

Hamid_0311 پاسخ داده:

RE: تشخیص قطعی بودن زبان مستقل از متن

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

ارسال:
  

moloodi پاسخ داده:

RE: تشخیص قطعی بودن زبان مستقل از متن

[quote='Hamid_0311' pid='325656' dateline='1420677761']
با سلام دوست عزیز پاسختون اشتباه دقت کنید
بله بله درست میگید من فک کردم a, b اول مستقل از یکدیگه ان.
یافتن تمامی ارسال‌های این کاربر

۰
ارسال:
  

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

RE: تشخیص قطعی بودن زبان مستقل از متن

کدوم رو کابر مولودی اشتباه جواب دادن؟ اخری که مستقل از متن غیر قطعیه که

ارسال:
  

moloodi پاسخ داده:

RE: تشخیص قطعی بودن زبان مستقل از متن

(۱۱ بهمن ۱۳۹۳ ۰۸:۰۸ ب.ظ)ریحان نوشته شده توسط:  کدوم رو کابر مولودی اشتباه جواب دادن؟ اخری که مستقل از متن غیر قطعیه که
درست میگه من یکجا اشتباه کرده بودم بعد ویرایش کردم.

آخری قطعیه.
یافتن تمامی ارسال‌های این کاربر

۰
ارسال:
  

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

RE: تشخیص قطعی بودن زبان مستقل از متن

اخه چرا قطعیه؟ این که خیلی مشهوره.غیر قطعی ام هست...چون نمیدونیم رلشته با A شروع میشه یا با B اگه با A شروع شه که به ازای a باید a پوش کنیم به ازای B باید A پاپ کنیم
اگه هم رشته با B شروع شه باید به ازای B علامت B پوش کنیم به ازای A علامتB را از استک پاپ کنیم....

پس برای دیدن A دوحالت پیش میاد یکی پوش A دیگری پاپ B
برای دیدن B هم همینطور دوحالت پیش میاد یا B را پوش میکنیم یا A پاپ میکنیم...

مگه نه؟

نمیدونم مکملش که هست گرامری که تعدادA ها مخالف تعدادB ها ست چرا قطعیه؟


تازه نمیدونمم گرامری که به فرم w مخالف W^R هست چرا قطعیه؟

ارسال:
  

moloodi پاسخ داده:

RE: تشخیص قطعی بودن زبان مستقل از متن

(۱۱ بهمن ۱۳۹۳ ۱۱:۰۸ ب.ظ)ریحان نوشته شده توسط:  اخه چرا قطعیه؟ این که خیلی مشهوره.غیر قطعی ام هست...چون نمیدونیم رلشته با A شروع میشه یا با B اگه با A شروع شه که به ازای a باید a پوش کنیم به ازای B باید A پاپ کنیم
اگه هم رشته با B شروع شه باید به ازای B علامت B پوش کنیم به ازای A علامتB را از استک پاپ کنیم....

پس برای دیدن A دوحالت پیش میاد یکی پوش A دیگری پاپ B
برای دیدن B هم همینطور دوحالت پیش میاد یا B را پوش میکنیم یا A پاپ میکنیم...

مگه نه؟

روش پذیرش قطعیشو اینجا گذاشتم .

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

۰
ارسال: #۱۰
  

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

RE: تشخیص قطعی بودن زبان مستقل از متن

میسیBlush



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  چرا مستقل از متنه؟ Wa^nb^mW^R poldasht ۱۱ ۳,۱۴۱ ۱۴ بهمن ۱۳۹۳ ۰۹:۱۰ ب.ظ
آخرین ارسال: ss.hoseini
  خواص مستقل از متن maryam.roshan ۳ ۲,۰۸۶ ۱۲ بهمن ۱۳۹۳ ۱۱:۰۱ ب.ظ
آخرین ارسال: fatemeh69
  چرا عکس نقیض لم تزریق مستقل از متن نشان دهنده نامنظم بودنه؟ ریحان ۷ ۲,۱۵۲ ۱۲ بهمن ۱۳۹۳ ۱۲:۱۳ ب.ظ
آخرین ارسال: ریحان
Question تشخیص زبان های مستقل از متن Ametrine ۹ ۴,۱۲۲ ۱۲ بهمن ۱۳۹۳ ۰۱:۵۱ ق.ظ
آخرین ارسال: ریحان
  چرا n(a)=!n(b) مستقل از متن قطعیه؟ ریحان ۸ ۲,۳۲۵ ۱۱ بهمن ۱۳۹۳ ۱۱:۰۲ ب.ظ
آخرین ارسال: ریحان
  منظم بودن uww^R v nazanin2020 ۵ ۲,۱۲۶ ۱۱ بهمن ۱۳۹۳ ۱۰:۱۵ ب.ظ
آخرین ارسال: nazanin2020
  آیا این زبان مستقل از متن است؟؟ K<=max(i,j) Imankhani ۸ ۲,۶۹۲ ۱۱ بهمن ۱۳۹۳ ۰۷:۴۷ ب.ظ
آخرین ارسال: ریحان
  تشخیص اجتماع و اشتراک یک زبان جساس به متن با مستقل از متن یا منظم maryam.roshan ۱ ۱,۴۳۳ ۱۱ بهمن ۱۳۹۳ ۱۲:۴۳ ق.ظ
آخرین ارسال: fatemeh69
  شمارا بودن یا نبودن زبانهای R و RE pooyaa ۶ ۲,۸۸۱ ۱۱ بهمن ۱۳۹۳ ۱۲:۲۱ ق.ظ
آخرین ارسال: fatemeh69
  نحوه تشخیص زبان های خطی arefeh.hp ۷ ۴,۲۶۴ ۰۹ بهمن ۱۳۹۳ ۰۱:۰۵ ق.ظ
آخرین ارسال: nazanin2020

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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