با عرض سلام
دوستان لطف می کنید در مورد تشخیص زبان یک گرامر توضیح بفرمایید؟ مثلا توی سوالات زیر.
با سپاس فراوان
من دقیقا سوالتونو متوجه نشدم ولی تا حد امکان توضیح می دم
ببین چهار تا دسته بندی برای زبان ها داریم
زبان های منظم :این زبان ها کلا یک متغیر در سمت راست قواعد دارند که می تونه تو منتهی الیه سمت چپ باشه یا سمت راست که میشه منظم از چپ یا از راست.
زبان های مستقل از متن:این زبان های می تونند هرتعداد متغیر یا non terminal در سمت راست قواعدشون داشته باشند بدون این که محدودیتی در مکان متغیرهاشون داشته باشند
همین جا توی پرانتز بگم که زبان های خطی جز این دسته بندی محسوب نمی شن این زبانها کلا یک متغیر می تونند توی سمت راستشون داشته باشن بدون اینکه در محل اون محدودیتی وجود داشته باشه در واقع این خطی ها با مستقل از متنها هم اشتراک دارند علاوه بر اینکه منظم ها را هم پوشش می دهند
حالا مستقل از متن می تونه معین باشه یا نامعین .در واقع اگر در یک جایی از رشته به عدم قطعیت برخورد کنیم اون مستقل از متن می تونه نامعین باشه در واقع اگر با قطعیت نتونیم بگیم می شه غیر قطعی(کلاس ماشینهای غیرقطعی با کلاس قطعی ها هم ارز نیست برعکس منظمها)
زبانهای حساس به متن:که هم سمت چپ و هم سمت راست می تونیم متغیر داشته باشم اما باید دقت کنیم که طول سمت چپها همیشه از سمت راست قواعد کوچکتر مساوی باشه
آخرش هم که زبانهای بدون محدودیت رو داریم که می شه هم ارز تورینگها
سلام دوست عزیز
مرسی از جوابتون
می خواستم بدونم با این تعریف ها ، چه جوری می تونم سوالات رو حل کنم؟
اگه لطف کنید رو سوالات تصویر ، راه حل رو توضیح بدید ممنون می شم
موفق باشید
[attachment=21588]این حل یکی از سوالها
(۲۵ فروردین ۱۳۹۶ ۰۳:۱۵ ب.ظ)mahsap91 نوشته شده توسط: این حل یکی از سوالها
خیلی لطف کردی دوست گرامی
موفق و پیروز باشید
(۲۵ فروردین ۱۳۹۶ ۰۳:۲۱ ب.ظ)alimamala نوشته شده توسط:خواهش می کنم شما هم همین طور(25 فروردین ۱۳۹۶ ۰۳:۱۵ ب.ظ)mahsap91 نوشته شده توسط: این حل یکی از سوالها
خیلی لطف کردی دوست گرامی
موفق و پیروز باشید
(۲۵ فروردین ۱۳۹۶ ۰۳:۱۵ ب.ظ)mahsap91 نوشته شده توسط: این حل یکی از سوالهاسلام
بااحترام به پاسختان
به نظر به جز زبان اول ۳ زبان دیگر قطعی هستند
[tex]L=\{w\in\{a,b\}^{\ast}\: |\: n_a(w)\: \ne n_b(w)\}[/tex] یک زبان مستقل از متن قطعی است(از تمرینات لینز)
[tex]\{a^nb^n\: |\: n\ge0\}\: \cup\: \{b^na^n\: |\: n\ge0\}[/tex] یک زبان مستقل از متن قطعی است چون اولین نماد رشته ورودی مشخص می کند در کدام مسیر باید حرکت کردو انتخاب دیگری نداریم این زبان را با زبان اول مقایسه کنید در انجا مشخص نیست که تعداد a را باید بشماریم یا نه یعنی وقتی a در ابتدای رشته ورودی امد دو حالت داریم بررسی برابری a با b یا نادیده گرفتن تعداد a و بررسی تعداد b با c و لی در این زبان در همان ابتدای رشته ورودی مشخص است در کدام مسیر باید حرکت کرد.
[tex]\{a^ib^jc^k\: |\: j=i+k\}[/tex] هم به نظر مستقل از متن قطعی است .در واقع مرز بین اینکه باید از پشته A را پاپ کنیم ویا B پوش کنیم را خالی بودن پشته و نماد جاری ورودی به قطعی مشخص می کند و غیر غطعیتی نداریم.در واقع بعد از این که A ها از پشته پاپ شدند و پشته خالی شد با دیدن b دیگر B را پوش تا به c برسیم
به نظر جواب این تست (۳۴۹ تصویر)گزینه ۳ باشد