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

چرا n(a)=!n(b) مستقل از متن قطعیه؟

ارسال:
  

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

چرا n(a)=!n(b) مستقل از متن قطعیه؟

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

۲
ارسال:
  

Jooybari پاسخ داده:

RE: چرا این زبان مستقل از متن قطعیه؟

سلام. فرقی نمیکنه رشته با چی شروع میشه. فقط به موارد زیر توجه کنید:

اگه حرف خونده شده a بود به پشته نگاه میکنیم. اگه داخل پشته Z یا A بود به بالای پشته یه A اضافه میکنیم. اگه بالای پشته B بود اون B رو حذف میکنیم.
اگه حرف خونده شده b بود به پشته نگاه میکنیم. اگه داخل پشته Z یا B بود به بالای پشته یه B اضافه میکنیم. اگه بالای پشته A بود اون A رو حذف میکنیم.
وقتی رشته تموم شد نباید حرف بالای پشته Z باشه. برای حفظ قطعیت باید اولین حرف A یا B که در پشته روی Z قرار میگیره رو با یه شکل دیگه مثل a و b بنویسیم که بدونیم کی قراره به حالت غیر پایانی بریم. به نظرم ماشین قطعیش با ۲ حالت قابل پیاده سازیه.

۰
ارسال:
  

ana9940 پاسخ داده:

RE: چرا این زبان مستقل از متن قطعیه؟

فقط با زبان گفته مستقل متن نیست ؟ گرامرش هم بوده؟ از روی گرامر راحت میشه فهمید.

ارسال:
  

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

RE: چرا این زبان مستقل از متن قطعیه؟

(۲۹ دى ۱۳۹۳ ۰۳:۲۰ ب.ظ)ana9940 نوشته شده توسط:  فقط با زبان گفته مستقل متن نیست ؟ گرامرش هم بوده؟ از روی گرامر راحت میشه فهمید.

بله فقظ از روی زبان گفته

از روی گرامر چطوری مگه میشه فعمید؟ از روی زشته هاش میفهمین؟ یا مثلا اگه منظم بود میگیم مستقل از متن قطعیم هست؟
یافتن تمامی ارسال‌های این کاربر

ارسال:
  

ana9940 پاسخ داده:

RE: چرا این زبان مستقل از متن قطعیه؟

حدس میزنم میشه واسش گرامر مستقل از متن نوشت ولی من الان نتونستم بنویسم. Big Grin
از روی گرامرش میشه فهمید مستقل از متنه، گرامرهایی که در سمت راست شون فقط یک غیر پایانه وجود داشته ، مستقل از متن هستند.
مثل : [tex]s\: \longrightarrow\: aSb[/tex]

حالا این غیرپایانه اگه سمت راست ترین باشه ، میشه خطی مثل [tex]S\: \longrightarrow\: aS,\: S\longrightarrowSb[/tex]
اگه فقط خطی راست یا فقط خطی چپ باشه ، میشه منظم. یعنی اگه غیرپایانه ها در یک گرامر همیشه سمت چپ ترین باشه ، میشه خطی چپ و درنتیجه منظم.
من متاسفانه سرکارم و کتاب دنبالم نیست وگرنه این سوال و اونی که تفاوت ها زبانها بود رو با مثال توضیحش میدادم برات.
کلا نظریه رو با مثال حل کنی و یاد بگیری خیلی راحته.
یافتن تمامی ارسال‌های این کاربر

۰
ارسال:
  

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

RE: چرا این زبان مستقل از متن قطعیه؟

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

(۲۹ دى ۱۳۹۳ ۰۳:۴۰ ب.ظ)ana9940 نوشته شده توسط:  حدس میزنم میشه واسش گرامر مستقل از متن نوشت ولی من الان نتونستم بنویسم. Big Grin
از روی گرامرش میشه فهمید مستقل از متنه، گرامرهایی که در سمت راست شون فقط یک غیر پایانه وجود داشته ، مستقل از متن هستند.
مثل : [tex]s\: \longrightarrow\: aSb[/tex]

حالا این غیرپایانه اگه سمت راست ترین باشه ، میشه خطی مثل [tex]S\: \longrightarrow\: aS,\: S\longrightarrowSb[/tex]
اگه فقط خطی راست یا فقط خطی چپ باشه ، میشه منظم. یعنی اگه غیرپایانه ها در یک گرامر همیشه سمت چپ ترین باشه ، میشه خطی چپ و درنتیجه منظم.
من متاسفانه سرکارم و کتاب دنبالم نیست وگرنه این سوال و اونی که تفاوت ها زبانها بود رو با مثال توضیحش میدادم برات.
کلا نظریه رو با مثال حل کنی و یاد بگیری خیلی راحته.


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

۰
ارسال:
  

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

RE: چرا این زبان مستقل از متن قطعیه؟

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

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

ارسال:
  

ana9940 پاسخ داده:

RE: چرا این زبان مستقل از متن قطعیه؟

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

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

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

۰
ارسال:
  

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

RE: چرا این زبان مستقل از متن قطعیه؟

دستتون درد نکنه



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

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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